【訓練題9：多重背包的二進制拆分】寶物篩選 | 洛谷 P1776

難度

綠 題 綠題 綠題

題意

一個 普通 的多重背包
物品數 N N N 背包容積 V V V
每個物品有重量 w i w_i wi? 價值 v i v_i vi? 物品數 c i c_i ci?
求裝完之后的最大價值和

資料范圍

1 ≤ n ≤ 100 1\le n\le 100 1≤n≤100
0 ≤ V ≤ 4 × 1 0 4 0\le V\le 4\times10^4 0≤V≤4×104
∑ c i ≤ 1 0 5 \sum c_i\le 10^5 ∑ci?≤105

思路

【普通方法】

• 對于每個物品，可以選擇 1 ～ c i 1\sim c_i 1～ci?個
• 轉移： d p [ j ] = max ? { d p [ j ] , d p [ j ? k ? w [ i ] ] + k ? v [ i ] } dp[j]=\max\{dp[j],dp[j-k*w[i]]+k*v[i]\} dp[j]=max{dp[j],dp[j?k?w[i]]+k?v[i]}
• 時間復雜度 O ( N V ∑ c i ) O(NV\sum c_i) O(NV∑ci?)
• 經過一個數量回圈優化以及O2優化，可以勉強卡過去、、
• （開啟了O2優化之后的時間）

【二進制拆分】

• 重點來了！
• 由于一個物品數量特別多，我們需要對其進行優化，
• 假設一個物品有17個，我們可以把它拆成：17=1+2+4+8+2
• 前面幾個數分別是 2的冪次方 ， 最后一個數字為 個數減去前面的冪次方的和（或者叫做拆分的補足）
• 我們可以對這幾個數字進行選取，于是可以選出所有[1,17]范圍內的所有數字
• 選取數字的程序，正好就是01背包選取物品的程序，
• 這樣，每個物品的個數 C i C_i Ci? 被我們減少成 log ? C i \log C_i logCi?
• 總體時間復雜度即為 O ( N V ∑ log ? C i ) O(NV\sum\log C_i) O(NV∑logCi?)
• （同樣開啟了O2優化的二進制拆分的時間）
  
• （無O2優化的正常代碼時間）
  

核心代碼【普通多重背包】

時間復雜度 O ( N V ∑ C i ) O(NV\sum C_i) O(NV∑Ci?)

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 4e4+50;

int v[MAX];
int w[MAX];
int cnt[MAX];
int dp[MAX];
int main()
{
    int N,W;
    cin >> N >> W;
    for(int i = 1;i <= N;++i){
        cin >>  v[i] >> w[i] >> cnt[i];
    }
    for(int i = 1;i <= N;++i){
        for(int j = W;j >= w[i];--j){
            for(int k = 1;k <= cnt[i];++k){
                if(j - k * w[i] < 0)break;
                dp[j] = max(dp[j],dp[j - k * w[i]] + k * v[i]);
            }
        }
    }
    cout << dp[W];
    return 0;
}

核心代碼【二進制拆分】

時間復雜度 O ( N V ∑ log ? C i ) O(NV\sum\log C_i) O(NV∑logCi?)

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 2e5+50;

int v[MAX];
int w[MAX];
int dp[MAX];
int main()
{
    int N,W;
    int ct = 0;
    cin >> N >> W;
    for(int i = 1;i <= N;++i){
        int tx,ty,tz;
        cin >> tx >> ty >> tz;
        for(int j = 1;j <= tz;j <<= 1){
            v[++ct] = tx * j;
            w[ct]   = ty * j;
            tz -= j;
        }
        if(tz){
            v[++ct] = tx * tz;
            w[ct]   = ty * tz;
        }
    }
    for(int i = 1;i <= ct;++i){
        for(int j = W;j >= w[i];--j){
            dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
        }
    }
    cout << dp[W];
    return 0;
}