Onway

pku 1742 多重背包转完全背包

我觉得这个题目跟pku 1276 cash machine和pku 1882 stamps都有点像。
首先与1276 cash machine一样，都是价值等于重量的多重背包，但1276可以用二进制压缩物品转0-1背包，这个题

目当然也可以，但会超时。所以discuss有一帖说教主忽悠了大家。
与1882 stamps像，是因为是都是有张数限制，都是通过完全背包来做吧，个人觉得。只是张数限制稍有不同，一个

是单个物品张数，一个是所有物品张数。就因为这个，两个题一个分在多重背包，一个分在了完全背包。转完全背

包后，时间就可以变为O(N*M)了。

我是看《背包九讲》的二进制压缩物品，然后直接拿这个题开刀。超时几次后，上网找O(N*M)的算法途中，看到别

人的一点提示，发现跟1882可以一样做法。

题意：
有多种面值不同的硬币，每种硬币有多枚，给出一个数M，求出1到M之间，有多少个面值是可以通过这些硬币组成的

。

思路：
定义一个标记数组sgn[MAX+1]，将1到MAX之间的能组成的面值进行标记。一个张数统计数组num[MAX+1],表示对于第

i种硬币，当组成j面值时，使用的张数num[j]。
这里可能有一个比较绕的问题：过早的使用完了第i种硬币，会不会对第i+1种硬币进行策略的时候造成影响呢？答

案是会的，但正是需要这种影响。对第i+1种硬币进行策略组合的时候，正是建立在前i种硬币组成的基础上。
对已组合的面值j进行标记，一是因为这是后面组成面值的基础，二能保证对后面的硬币个数不会造成浪费。

 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}