Onway

pku 1276 价值等于重量的多重背包

题意：
取款机里有多种不同面值的钞票，各种面值的钞票的张数也不同，给出取款值CASH，问最多能拿出多少钱。

思路：
将钞票看成是价值等于重量的物品，取款值为背包容量，那么这个题就是一个典型的多重背包。
从数据规模考虑，直接变为0-1背包求解，O(CASH*NK*N)的时间肯定超时。参考《背包九讲》中的用二进制压缩

物品可以将时间优化为O(CASH*N*logNK)，这样可以变成物品个数不超过100个的0-1背包。
然后便是0-1背包的求解了。

失误：
由于第一次学多重背包，看到二进制压缩物品时，当时以为看懂了，提交后错了N多次，才发现压缩时的最后一

项系数搞错了。然后处理不好，又出现负数的情况，导致一直RE。修补压缩物品部分，感觉又长又臭，遂通过研

究一番将物品压缩部分缩小到11行。

 1#include <iostream>
 2#include <math.h>
 3using namespace std;
 4const int MAX=100005;
 5int w[150],dp[MAX+1];
 6struct deno
 7{
 8    int cnt;
 9    int num;
10}data[12];
11int main()
12{
13    int n,m;
14    while(scanf("%d",&n)!=EOF)
15    {
16        scanf("%d",&m);
17        int i,j,k=1,tmp;
18        for(i=1;i<=m;++i)
19            scanf("%d%d",&data[i].cnt,&data[i].num);
20
21        memset(dp,0,sizeof(dp));
22        memset(w,0,sizeof(w));
23
24        for(i=1;i<=m;++i)
25        {
26            j=0;
27            while(data[i].cnt+1>=pow(2.0,j+1))
28            {
29                tmp=pow(2.0,j++);
30                w[k++]=tmp*data[i].num;
31            }
32            tmp=data[i].cnt+1-pow(2.0,j);
33            if(tmp)
34                w[k++]=tmp*data[i].num;
35        }
36
37        for(i=1,--k;i<=k;++i)
38            for(j=MAX;j>=w[i];--j)
39                dp[j]=dp[j]>dp[j-w[i]]+w[i]?dp[j]:dp[j-w[i]]+w[i];
40
41        printf("%d\n",dp[n]);
42    }
43    return 0;
44}
45
46