HDU 2191悼念512汶川大地震遇难同胞――珍惜现在，感恩生活(多重背包)

?

假设你有资金n元, 然后有m种大米, 每种大米价格为cost[i], 重量为val[i], 数量为num[i]. 现在问你用n元钱最多能买多重的大米?

分析:

本题是典型的多重背包问题.

我们令dp[i][j]==x表示只购买前i种大米, 且总费用<=j时能购买的大米最大重量为x.

初始化: dp为全0.

由于每种大米有数量num[i], 所以我们分下面两种情况做:

当cost[i]*num[i]>=n时, 我们直接对该种大米做一次完全背包过程即可.

当 cost[i]*num[i]

1个(i类物品) 2个 4个 2^(k-1)个 以及 num[i]-2^k+1个

我们对上述k+1种新物品每个都做一个01背包即可覆盖我们可能对第i种物品做出的所有选择.

最终所求: dp[m][n]的值.

AC代码:

?

#include
  
   
#include
   
     #include
    
      using namespace std; const int maxn=4000+5; int n;//金额 int m;//大米种类 int cost[100+5];//价格 int val[100+5]; //重量 int num[100+5]; //数量 int dp[maxn]; //一次01背包 void ZERO_ONE_PACK(int cost,int val) { for(int i=n;i>=cost;i--) dp[i] = max(dp[i], dp[i-cost]+val); } //一次完全背包 void COMPLETE_PACK(int cost,int val) { for(int i=cost;i<=n;i++) dp[i] = max(dp[i], dp[i-cost]+val); } //一次多重背包 void MULTIPLE_PACK(int cost,int val,int num) { if(cost*num>=n) { COMPLETE_PACK(cost,val); return; } int k=1; while(k
     
      
?