Time Limit: 3000MS Memory Limit: 30000K
Total Submissions: 48194 Accepted: 16209
Description
Input
Output
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output
8
4
题意：有n种钱币，每种有个，价值为
，求这些钱币能凑出多少种小于等于m的金额。
题解：男人八题之一怎么可能用直接的多重背包就能解决。此题数据范围较大，多重背包会TLE。dp[i]不应该记录容量为i的背包最多能装多少，而应该记录是否能达到容量i。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100005;
int num[maxn],w[maxn],flag[maxn],cnt[maxn];
int main()
{
int i,j,n,m,ans;
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m) break;
{
fill(flag,flag+maxn,0);
flag[0]=1;
ans=0;
}
for(i=1;i<=n;i++) scanf("%d",&w[i]);
for(i=1;i<=n;i++) scanf("%d",&num[i]);
for(i=1;i<=n;i++)
{
fill(cnt,cnt+maxn,0);
for(j=w[i];j<=m;j++)
if(!flag[j]&&flag[j-w[i]]&&cnt[j-w[i]]+1<=num[i])
{
ans++;
flag[j]=1;
cnt[j]=cnt[j-w[i]]+1;
}
}
printf("%d\n",ans);
}
return 0;
}
原文：https://www.cnblogs.com/VividBinGo/p/11359071.html