Onway

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

題意：
取款機(jī)里有多種不同面值的鈔票，各種面值的鈔票的張數(shù)也不同，給出取款值CASH，問最多能拿出多少錢。

思路：
將鈔票看成是價值等于重量的物品，取款值為背包容量，那么這個題就是一個典型的多重背包。
從數(shù)據(jù)規(guī)模考慮，直接變?yōu)?-1背包求解，O(CASH*NK*N)的時間肯定超時。參考《背包九講》中的用二進(jìn)制壓縮

物品可以將時間優(yōu)化為O(CASH*N*logNK)，這樣可以變成物品個數(shù)不超過100個的0-1背包。
然后便是0-1背包的求解了。

失誤：
由于第一次學(xué)多重背包，看到二進(jìn)制壓縮物品時，當(dāng)時以為看懂了，提交后錯了N多次，才發(fā)現(xiàn)壓縮時的最后一

項(xiàng)系數(shù)搞錯了。然后處理不好，又出現(xiàn)負(fù)數(shù)的情況，導(dǎo)致一直RE。修補(bǔ)壓縮物品部分，感覺又長又臭，遂通過研

究一番將物品壓縮部分縮小到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