转载自:大神的标准CODE
给出硬币面额及每种硬币的个数,求从1到m能凑出面额的个数。
Input
多组数据,每组数据前两个数字为n,m。n表示硬币种类数,m为最大面额,之后前n个数为每种硬币的面额,后n个数为相应每种硬币的个数。 (n<=100,m<=100000,面额<=100000,每种个数<=1000)
Output
RT
Sample Input
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
Sample Output
8
4
#include<iostream>
#include<cstring>
using namespace std;
#define MAXV 105
#define MAXM 100005
int w[MAXV],c[MAXV],vis[MAXM],dp[MAXM];
int main(){
int i,j,n,m,ans;
while(scanf("%d%d",&n,&m) && n && m){
for(i=1;i<=n;i++)
scanf("%d",&w[i]);
for(i=1;i<=n;i++)
scanf("%d",&c[i]);
memset(vis,0,sizeof(vis));
vis[0]=1;ans=0;
for(i=1;i<=n;i++){
memset(dp,0,sizeof(dp));
for(j=w[i];j<=m;j++){
if(!vis[j] && vis[j-w[i]] && dp[j-w[i]]+1<=c[i]){
vis[j]=1;
dp[j]=dp[j-w[i]]+1;
ans++;
}
}
}
printf("%d\n",ans);
}
return 0;
}