多重背包
看了《背包九讲》，此题1A，爽！！！
根据《背包九讲》提供的伪代码：
procedure MultiplePack(cost,weight,amount) if cost*amount>=V CompletePack(cost,weight) return integer k=1 while k<num ZeroOnePack(k*cost,k*weight) amount=amount-k k=k*2 ZeroOnePack(amount*cost,amount*weight)
自己写一个吧，哈哈
View Code
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int a[12],b[12]; bool dp[100002]; int main() { int m, n, i, j; while(~scanf("%d%d",&m,&n)) { for(i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); memset(dp,0,sizeof(dp)); dp[0]=1; for(i=1;i<=n;i++) { if(a[i]*b[i]>=m) { for(j=0;j<=m;j++) if(j>=b[i]&&dp[j-b[i]])dp[j]=1; } else { int k=1; while(k<a[i]) { for(j=m;j>=0;j--) if(j>=b[i]*k&&dp[j-b[i]*k])dp[j]=1; a[i]-=k; k*=2; } for(j=m;j>=0;j--) if(j>=a[i]*b[i]&&dp[j-b[i]*a[i]])dp[j]=1; } } for(i=m;i>=0;i--) if(dp[i]){printf("%d\n",i);break;} } return 0; }
差不多，循环次数少了一些。
View Code
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int a[12],b[12]; bool dp[100002]; int main() { int m, n, i, j; while(~scanf("%d%d",&m,&n)) { for(i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); memset(dp,0,sizeof(dp)); dp[0]=1; for(i=1;i<=n;i++) { if(a[i]*b[i]>=m) { for(j=b[i];j<=m;j++) if(dp[j-b[i]])dp[j]=1; } else { int k=1; while(k<a[i]) { for(j=m;j>=b[i]*k;j--) if(dp[j-b[i]*k])dp[j]=1; a[i]-=k; k*=2; } for(j=m;j>=a[i]*b[i];j--) if(dp[j-b[i]*a[i]])dp[j]=1; } } for(i=m;i>=0;i--) if(dp[i]){printf("%d\n",i);break;} } return 0; }