DP专题|多重背包问题和“二进制拆分”

预告:我用两年写的新书《算法竞赛》,已于2022年2月交给清华大学出版社,预计于2022年7月出版。《算法竞赛》是一本“大全”,内容覆盖“基础-中级-高级”,篇幅700页左右。部分知识点的草稿已经在本博客发表。本篇博客节选自新书《算法竞赛》的“5.2 经典线性DP问题”。

文章目录

  • 1、多重背包问题的简单DP解法
  • 2、用“二进制拆分”优化求解多重背包
  • 3、用单调队列优化解多重背包

【DP专题|多重背包问题和“二进制拆分”】?? 多重背包问题:给定 n n n种物品和一个背包,第 i i i种物品的体积是 c i c_i ci?,价值为 w i w_i wi?,并且有 m i m_i mi?个,背包的总容量为 C C C。如何选择装入背包的物品,使得装入背包中的物品的总价值最大?
?? 这是一个经典的DP问题,是0/1背包问题的扩展。具体描述见下面的例题。
宝物筛选 洛谷 P1776 https://www.luogu.com.cn/problem/P1776
输入:第一行是整数n n n和 C C C,分别表示物品种数和背包的最大容量。
接下来n n n 行,每行三个整数w i 、 c i 、 m i w_i、c_i、m_i wi?、ci?、mi?,分别表示第 i i i个物品的价值、体积、数量。
输出:输出一个整数,表示背包不超载的情况下装入物品的最大价值。
?? 这里给出3种DP解法。推荐第2种解法,它把多重背包转化为:“二进制优化+0/1背包”。
1、多重背包问题的简单DP解法 ?? 有两种思路。
?? 第一种思路,转换为0/1背包问题。把相同的 m i m_i mi?个第 i i i种物品看成独立的 m i m_i mi?个,总共 ∑ i = 1 n m i \sum_{i=1}^nm_i ∑i=1n?mi?个物品,然后按0/1背包求解,复杂度 O ( C × ∑ i = 1 n m i ) O(C\times\sum_{i=1}^nm_i) O(C×∑i=1n?mi?)。
?? 第二种思路,直接求解。定义状态 d p [ i ] [ j ] dp[i][j] dp[i][j]:表示把前 i i i个物品装进容量 j j j的背包,能装进背包的最大价值。第 i i i个物品分为装或不装两种情况,得到多重背包的状态转移方程:
dp[i][j] = max{dp[i-1][j], dp[i-1][j-k*c[i]] + k*w[i]} 1 ≤ k ≤ min{m[i], j/c[i]}

?? 代码直接写 i 、 j 、 k i、j、k i、j、k三重循环,复杂度和第一种思路的复杂度一样。下面用滚动数组编码,提交判题后会超时。
//洛谷 P1776:滚动数组版本的多重背包(超时TLE) #include using namespace std; const int N=100010; int n,C,dp[N]; int w[N],c[N],m[N]; //物品i的价值、体积、数量 int main(){ cin >> n >> C; //物品数量,背包容量 for(int i=1; i<=n; i++) cin>>w[i]>>c[i]>>m[i]; //以下是滚动数组版本的多重背包 for(int i=1; i<=n; i++)//枚举物品 for(int j=C; j>=c[i]; j--)//枚举背包容量 for(int k=1; k<=m[i] && k*c[i]<=j; k++) dp[j] = max(dp[j],dp[j-k*c[i]]+k*w[i]); cout << dp[C] << endl; return 0; }

2、用“二进制拆分”优化求解多重背包 ?? 这是一种简单而有效的技巧。在解法 1 1 1的基础上加上这个优化,能显著改善复杂度。
?? 原理很简单,例如第 i i i种物品有 m i m_i mi? = 25个,这25个物品放进背包的组合,有0 ~ 25的26种情况。不过要组合成26种情况,其实并不需要25个物品,5个就够了。根据二进制的计算原理,任何一个十进制整数 X X X,都可以用1、2、4、8、…这些2的倍数相加得到,例如25 = 16 + 8 + 1,这些2的倍数只有 l o g 2 X log_2X log2?X个。题目中第 i i i种物品有 m i m_i mi?个,用 l o g 2 m i log_2m_i log2?mi?个数就能组合出0 ~m i m_i mi?种情况。
?? 总复杂度从 O ( C × ∑ i = 1 n m i ) O(C\times\sum_{i=1}^nm_i) O(C×∑i=1n?mi?)优化到了 O ( C × ∑ i = 1 n l o g 2 m i ) O(C\times\sum_{i=1}^nlog_2m_i) O(C×∑i=1n?log2?mi?),已经足够好了。
?? 注意拆分的具体实现,不能全部拆成2的倍数,而是先按2的倍数从小到大拆,最后是一个小于等于最大倍数的余数。
??对 m i m_i mi?这样拆分非常有必要,能够保证拆出的数相加在[1,m i m_i mi?]范围内,不会大于 m i m_i mi?。例如 m i m_i mi? = 25,把它拆成1、2、4、8、10,最后是余数10,10 < 16 = 24,读者可以验证用这5个数能组合成1~25内的所有数字,不会超过25。如果把25拆成1、2、4、8、16,相加的范围就是[1, 31]了。
??二进制优化之后,这个问题就变成了一个正常的0/1背包问题。所以,多重背包的解法是:二进制优化 + 0/1背包。
//洛谷 P1776:二进制拆分+滚动数组 #include using namespace std; const int N=100010; int n,C,dp[N]; int w[N],c[N],m[N]; int new_n; //二进制拆分后的新物品总数量 int new_w[N],new_c[N],new_m[N]; //二进制拆分后新物品 int main(){ cin >> n >>C; for(int i=1; i<=n; i++) cin>>w[i]>>c[i]>>m[i]; //以下是二进制拆分 int new_n = 0; for(int i=1; i<=n; i++){ for(int j=1; j<=m[i]; j<<=1) {//二进制枚举:1,2,4... m[i]-=j; //减去已拆分的 new_c[++new_n] = j*c[i]; //新物品 new_w[new_n]= j*w[i]; } if(m[i]){//最后一个是余数 new_c[++new_n] = m[i]*c[i]; new_w[new_n]= m[i]*w[i]; } } //以下是滚动数组版本的0/1背包 for(int i=1; i<=new_n; i++)//枚举物品 for(int j=C; j>=new_c[i]; j--)//枚举背包容量 dp[j] = max(dp[j],dp[j-new_c[i]]+new_w[i]); cout << dp[C] << endl; return 0; }

?? 解法2可以看作多重背包问题的标准解法,不过,还有更优的解法3。
3、用单调队列优化解多重背包 ?? 这种方法的复杂度为 O ( n C ) O(nC) O(nC),是最优的解法。
?? DP的单调队列优化比较复杂,蓝桥杯省赛估计用不着。
?? 详情见将出版的《算法竞赛》“5.8 单调队列优化”。如果想提前了解,这部分已经发表在博客里:单调队列DP优化

    推荐阅读