http://poj.org/problem?id=1742
ｎ个硬币，面值分别是A1...An,对应的数量分别是C1....Cn.用这些硬币组合起来能得到多少种面值不超过m的方案。
多重背包，不过这题很容易超时，用背包九讲的代码有人说行，但是我提交还是超时，后来参考别人代码加了一些优化才能过，有时间要去搞清楚多重背包的单调队列优化。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; bool dp[];
int n,m;
int p[],q[]; void ZeroOnePack(int cost)
{
int i;
for(i=m;i>=cost;i--)
{
dp[i]|=dp[i-cost];
}
} void CompletePack(int cost)
{
int i;
for(i=cost;i<=m;i++)
{
dp[i]|=dp[i-cost];
}
} void MultiplePack(int cost,int amount)
{
if(cost*amount>=m)
{
CompletePack(cost);
return;
}
int k=;
while(k<amount)
{
ZeroOnePack(k*cost);
amount-=k;
k*=;
}
ZeroOnePack(amount*cost);
} int main()
{
int i;
while(~scanf("%d%d",&n,&m))
{
if(n==&&m==) break;
for(i=;i<n;i++) scanf("%d",&p[i]);
for(i=;i<n;i++) scanf("%d",&q[i]);
for(i=;i<=m;i++) dp[i]=;
// dp[0]=1;
for(i=;i<n;i++)
{
MultiplePack(p[i],q[i]);
}
int res=;
for(i=;i<=m;i++)
if(dp[i]) res++;
printf("%d\n",res);
}
return ;
}