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