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