题意：有n种面值的硬币a[i],每种硬币有c[i]个，问能组成不大于m面值（1~m）的个数。
多重背包模板：by背包九讲。
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<map>
#include<cmath>
#include<iostream>
#include <queue>
#include <stack>
#include<algorithm>
#include<set>
using namespace std;
#define INF 1e8
#define eps 1e-8
#define LL long long
#define maxn 100001
#define mol 1000000007
//procedure MultiplePack(cost,weight,amount)
// if cost*amount>=V
// CompletePack(cost,weight)
// return
// integer k=1
// while k<amount
// ZeroOnePack(k*cost,k*weight)
// amount=amount-k
// k=k*2
// ZeroOnePack(amount*cost,amount*weight)
int n,m,a[110],c[110];
int dp[maxn];
void CompletePack(int cost,int weight)//全然背包
{
for(int v=cost;v<=m;v++)
dp[v]=max(dp[v],dp[v-cost]+weight);
}
void ZeroOnePack(int cost,int weight)//01背包
{
for(int v=m;v>=cost;v--)
dp[v]=max(dp[v],dp[v-cost]+weight);
}
void MultiplePack(int cost,int weight,int amount)
{
if(cost*amount>=m)
CompletePack(cost,weight);
else
{
int k=1;
while( k<amount)//二进制拆分
{
ZeroOnePack(k*cost,k*weight);
amount=amount-k;
k=k*2;
}
ZeroOnePack(amount*cost,amount*weight);
}
}
int main()
{
while(scanf("%d%d",&n,&m))
{
if(n==0&&m==0) break;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=m;i++) dp[i]=0;
for(int i=1;i<=n;i++)
MultiplePack(a[i],a[i],c[i]);
int ans=0;
for(int i=1;i<=m;i++)
if(dp[i]==i)
ans++;
printf("%d
",ans);
}
return 0;
}
/*
3 10
1 2 4 2 1 1
2 5
1 4 2 1
*/