HDU1114 Piggy-Bank 完全背包

题意：

给出一个存钱罐的空罐时的质量和装了钱之后的质量，再给出一些硬币的质量和相应的价值，问存钱罐里的钱最少可能为多少。

这道题就是完全背包的问题，注意初始化。

完全背包与01背包不同的是第二次遍历的时候要顺序而已。

初始化，这道题要求背包恰好装满，而且要求的值尽量少，所以dp[0]=0;其余设为无穷大。

1.若没有要求恰好装满，则全为0.

2.若要求的值尽量大，则dp[0]=0;其余为无穷小。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
const int inf=0x3f3f3f3f;
int dp[maxn];
int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        int e,f;
        scanf("%d%d",&e,&f);
        int m=f-e;
        dp[0]=0;
        for(int i=1;i<=m;i++)
            dp[i]=inf;
        int p,w,n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p,&w);
            for(int j=w;j<=m;j++)
            {
                dp[j]=min(dp[j],dp[j-w]+p);
            }
        }
        if(dp[m]==inf)
            printf("This is impossible.
");
        else
            printf("The minimum amount of money in the piggy-bank is %d.
",dp[m]);
    }
    return 0;
}