白书P60

白书P60 - 硬币问题

 完全背包、DP

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define N 1010

int n,s;
int w[N];             //w表示n种硬币的面值
int dp1[N];           //dp1[j]表示刚好凑足j的最少硬币数
int dp2[N];           //dp2[j]表示刚好凑足j的最多硬币数

int main()
{
    int i,j;
    while(scanf("%d%d",&n,&s)!=EOF)
    {
        memset(dp1,INF,sizeof(dp1));
        memset(dp2,-INF,sizeof(dp2));
        dp1[0]=0;
        dp2[0]=0;
        
        for(i=1;i<=n;i++)
        {
            scanf("%d",&w[i]);
        }

        for(i=1;i<=n;i++)
        {
            for(j=w[i];j<=s;j++)
            {
                dp1[j]=min(dp1[j],dp1[j-w[i]]+1);
                dp2[j]=max(dp2[j],dp2[j-w[i]]+1);
            }
        }
        cout<<dp1[s]<<' '<<dp2[s]<<endl;
    }
    return 0;
}