Onway

pku 1276 價(jià)值等于重量的多重背包

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

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

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

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

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

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