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

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