Onway

pku 1742 多重背包轉完全背包

我覺得這個題目跟pku 1276 cash machine和pku 1882 stamps都有點像。
首先與1276 cash machine一樣，都是價值等于重量的多重背包，但1276可以用二進制壓縮物品轉0-1背包，這個題

目當然也可以，但會超時。所以discuss有一帖說教主忽悠了大家。
與1882 stamps像，是因為是都是有張數(shù)限制，都是通過完全背包來做吧，個人覺得。只是張數(shù)限制稍有不同，一個

是單個物品張數(shù)，一個是所有物品張數(shù)。就因為這個，兩個題一個分在多重背包，一個分在了完全背包。轉完全背

包后，時間就可以變?yōu)镺(N*M)了。

我是看《背包九講》的二進制壓縮物品，然后直接拿這個題開刀。超時幾次后，上網(wǎng)找O(N*M)的算法途中，看到別

人的一點提示，發(fā)現(xiàn)跟1882可以一樣做法。

題意：
有多種面值不同的硬幣，每種硬幣有多枚，給出一個數(shù)M，求出1到M之間，有多少個面值是可以通過這些硬幣組成的

。

思路：
定義一個標記數(shù)組sgn[MAX+1]，將1到MAX之間的能組成的面值進行標記。一個張數(shù)統(tǒng)計數(shù)組num[MAX+1],表示對于第

i種硬幣，當組成j面值時，使用的張數(shù)num[j]。
這里可能有一個比較繞的問題：過早的使用完了第i種硬幣，會不會對第i+1種硬幣進行策略的時候造成影響呢？答

案是會的，但正是需要這種影響。對第i+1種硬幣進行策略組合的時候，正是建立在前i種硬幣組成的基礎上。
對已組合的面值j進行標記，一是因為這是后面組成面值的基礎，二能保證對后面的硬幣個數(shù)不會造成浪費。

 1#include <iostream>
 2using namespace std;
 3const int MAX=100000;
 4bool sgn[MAX+1];
 5int cnt[MAX+1];
 6int a[101],c[101];
 7int main()
 8{
 9    int n,m;
10    while(scanf("%d%d",&n,&m)&&(n||m))
11    {
12        int i,j;
13        for(i=1;i<=n;++i)    scanf("%d",&a[i]);
14        for(i=1;i<=n;++i)    scanf("%d",&c[i]);
15        memset(sgn,0,sizeof(sgn));
16        sgn[0]=1;
17
18        for(i=1;i<=n;++i)
19        {
20            memset(cnt,0,sizeof(cnt));
21            for(j=a[i];j<=MAX;++j)
22                if(!sgn[j]&&sgn[j-a[i]]&&cnt[j-a[i]]<c[i])
23                {
24                    cnt[j]=cnt[j-a[i]]+1;
25                    sgn[j]=1;
26                }
27        }
28
29        for(i=1,j=0;i<=m;++i)
30            if(sgn[i])
31                ++j;
32
33        printf("%d\n",j);
34    }
35    return 0;
36}