多重背包的二进制拆分

• • 难度
  • 题意
  • 数据范围
  • 思路
  • 核心代码【普通多重背包】
  • 核心代码【二进制拆分】

难度

绿 题 绿题 绿题

题意

一个 普通 的多重背包
物品数 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​)

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​)

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;
}