HDU 1059 Dividing(多重背包)

HDU 1059 Dividing(多重背包)

題意:

現在有價值為1,2,3,4,5,6的6種物品, 它們的數量為num[i]( 1<=i<=6 )個. 現在要問的是能否把所有的的物品分成兩份且這兩份物品的價值總和相同 ?

分析:

首先我們求出所有物品的價值和sum_val, 如果sum_val是奇數, 那麼明顯不能分. 那麼sum_val為偶時, 我們令m=sum_val/2. 我能只要看看從所有物品裡面取物品能否使得: “所有取的物品總價值==m?”

由於每個物品的數目是num[i]個, 所以本題是一個多重背包問題.

其實多重背包問題可以轉成01背包來解, 但是效率不高. 所以這裡我們按<<背包九講>>中提到的二進制壓縮的思想來解決本題.

令dp[i][j]==x 表示選前i種物品且總價值<=j的前提下, 所有被選物品能達到的最大價值.

對於val[i]*num[i]>=m的物品來說, 我們直接用一次完全背包即可.

即dp[i][j] = max( dp[i-1][j] , dp[i][j-val[i]]+val[i] )

對於val[i]*num[i]

1個 2個 4個… 2^(k-1)個 以及 num[i] – 2^k+1 個

我們對由第i種物品劃分成的上述每堆物品做一次01背包即可.

(為什麼上面的劃分能得到正確解? 因為上面的物品覆蓋了我們對num[i]個第i類物品的所有可能選擇)

最終所求: 看dp[n][m]是否等於m即可.

AC代碼:

#include
#include
#include
using namespace std;
const int maxn=20000+5;

int m;//DP最大不能超過的價值
int dp[maxn*5];
int val[]={1,2,3,4,5,6};//每種物品的價值
int num[10];            //每種物品的數量

//一次01背包過程
void ZERO_ONE_PACK(int cost,int val)
{
    for(int i=m;i>=cost;i--)
        dp[i] = max(dp[i], dp[i-cost]+val);
}


//一次完全背包過程
void COMPLETE_PACK(int cost, int val)
{
    for(int i=cost;i<=m;i++)
        dp[i] = max(dp[i], dp[i-cost]+val);
}

//一次多重背包過程
void MULTIPLE_PACK(int cost,int val,int sum)
{
    //完全背包
    if(cost*sum>=m)
    {
        COMPLETE_PACK(cost,val);
        return ;
    }

    //log(sum)次01背包
    int k=1;
    while(k