Onway

 pku 1384 Piggy-Bank 完全背包。

正如网上说的，这是个挺裸的背包了。做了几个背包的题后看到这题，感觉就挺简单了。

这里需要注意的是首先要能判断题目有没有解，有解的情况下要找出最小解。

思路依然是数组标记的方法，对于第j面值，如果第j-w[i]面值有解，则j面值肯定有解。

这时要找最小解。要注意的是，如果j面值当前是0的话，首先为了确保有解，这时不用找最小解，直接加过去就得。

 1#include <iostream>
 2    using namespace std;
 3    const int MAX=10000;
 4    int w[MAX+1],v[MAX+1];
 5    int dp[MAX+1];
 6    bool sgn[MAX+1];
 7    int main()
 8    {
 9        int t;
10        scanf("%d",&t);
11        while(t--)
12        {
13            int start,end,n,i,j;
14            scanf("%d%d%d",&start,&end,&n);
15            for(i=1;i<=n;++i)
16                scanf("%d%d",&v[i],&w[i]);
17
18            memset(dp,0,sizeof(dp));
19            memset(sgn,0,sizeof(sgn));
20            sgn[0]=1;
21            for(i=1;i<=n;++i)
22                for(j=w[i];j<=MAX;++j)
23                    if(sgn[j-w[i]]&&dp[j]!=0)
24                    {
25                        dp[j]=dp[j]<dp[j-w[i]]+v[i]?dp[j]:dp[j-w[i]]+v[i];
26                        sgn[j]=1;
27                    }
28                    else if(sgn[j-w[i]]&&dp[j]==0)
29                    {
30                        dp[j]=dp[j-w[i]]+v[i];
31                        sgn[j]=1;
32                    }
33
34            if(dp[end-start]==0)
35                printf("This is impossible.\n");
36            else
37                printf("The minimum amount of money in the piggy-bank is %d.\n",dp[end-start]);
38        }
39        return 0;
40    }
41