POJ 1742 Coins G++ 二进制优化转化为01背包未实现 多重背包 背

#include <iostream> #include <cstring> using namespace std; //抄博友程序 二进制优化转化为01背包未实现 多重背包 背 int dp[100008]; int val[108]; int c[108]; int sum[100008];//使用硬币数 int main() { while(1) { memset(dp,0,sizeof(dp)); int n,m; cin>>n>>m; if(n==0 && (m==0)) { break; } for(int i=0;i<n;i++) { cin>>val[i]; } for(int i=0;i<n;i++) { cin>>c[i]; } dp[0]=1; for(int i=0;i<n;i++) { memset(sum,0,sizeof(sum)); for(int j=val[i];j<=m;j++) { if(dp[j]==0 && dp[j-val[i]]==1 && sum[j-val[i]]<c[i])//背 dp[j]==0 必须加 已实现的不用再浪费硬币 { sum[j]=sum[j-val[i]]+1; dp[j]=1; } } /* for(int j=1;j<=m;j++) { cout<<dp[j]<<" "; } cout<<endl;*/ } int jg=0; for(int i=1;i<=m;i++) { if(dp[i]==1) { jg++; } } cout<<jg<<endl; } return 0; }