赤裸裸的多重背包问题;
方法一:直接三重循环,这种方法会超时地……
for(i=1; i<=n; i++) { for(j=cash; j>=dk[i]; j--) { for(k=1; k<=nk[i]; k++) { if( j<k*dk[i]) break; if( dp[j]<dp[j-k*dk[i]]+k*dk[i]) dp[j]=dp[j-k*dk[i]]+k*dk[i]; } } }
方法二:二进制划分,将同种物品,以二进制划分的方式合并,大大减少了物品数量,然后以0 1背包的方法……
代码如下:
#include<stdio.h> #include<string.h> int main() { int cash, n; int dk[11], nk[11],dp[100001]; int i, j, k, temp; while( scanf("%d %d", &cash, &n)!=EOF ) { memset(dp, 0, sizeof(dp)); for(i=1; i<=n; i++) scanf("%d %d", nk+i, dk+i); for(i=1; i<=n; i++) { for(k=1; k<=nk[i]; k*=2)//二进制划分 { nk[i]-=k; temp=k*dk[i]; for(j=cash; j>=temp; j--)//0,1背包 { if( dp[j]<dp[j-temp]+temp) dp[j]=dp[j-temp]+temp; } } if( nk[i]>0 ) { temp=nk[i];*dk[i]; for(j=cash; j>=temp; j--)//0,1背包 { if( dp[j]<dp[j-temp]+temp) dp[j]=dp[j-temp]+temp; } } } printf("%d\n",dp[cash]); } }