第五课《分身术卷轴——二进制优化》
🎒故事开始：阿宝的新烦恼
1、上一课，阿宝学会了：
🌟多重背包
2、每种物品有固定数量。
例如：
| 宝剑 | 2 | 3 | 3把 |
可以拿：
0把
1把
2把
3把
3、状态转移：
dp[i][j]
=
max(
dp[i-1][j-k*w[i]]
+
k*v[i]
)
其中：
k
表示拿几件。
阿宝觉得很不错。
4、结果第二天，国王拿来了一张清单：
| 药水 | 2 | 3 | 1000瓶 |
……..
5、阿宝当场傻眼：
for(k=0;k<=1000;k++)
？
如果有很多种物品：
100种
每种：
1000件
程序会慢得像乌龟一样！
🐢🐢🐢
到底怎么办呢？
第一幕：神秘二进制登场
1、阿宝找到汉克老师。
汉克老师拿出一本算法书：
📜《二进制组合术》
2、汉克老师说：
阿宝，
其实1000件物品，
不需要一件一件处理！
3、阿宝：
什么？
难道还能合并？
4、汉克老师：
不仅能合并，
还能变成01背包！
第二幕：先理解二进制的力量
1、假设有：
13把宝剑
2、阿宝想：
0把
1把
2把
3把
…
13把
都要枚举。
3、汉克老师说：
我们换一种方法：
我们把13拆开。
拆成：
1
2
4
6
4、阿宝：
为什么是这样？
5、因为：
1
+
2
+
4
+
6
=
13
6、更神奇的是：
利用这4组，
我们能拼出：
0~13
所有数量！
7、例如：
（1）7把
1+2+4
（2）10把
4+6
（3）13把
1+2+4+6
全部都能表示！
第三幕：为什么要拆成1、2、4？
1、因为：
1
2
4
8
16
32
…
是：
🌟二进制
2、例如：
（1）13
二进制：
1101
（2）表示：
8
+
4
+
1
（3）所以：
任何数字都能由：
1
2
4
8
16
…
组合出来。
第四幕：真正的拆分方法
1、假设：
数量 = 13
（1）第一组：
1
剩：
12
（2）第二组：
2
剩：
10
（3）第三组：
4
剩：
6
（4）第四组：
剩余不足8。
直接全部拿走：
6
（5）得到：
1
2
4
6
2、🌟万能拆分代码
int cnt = s;
for(int k=1;k<=cnt;k*=2)
{
cnt -= k;
}
最后剩余部分单独处理。
3、另一种写法：
int k = 1;
while(k <= s)
{
s -= k;
k *= 2;
}
竞赛中一般写成下面这种模板。
第五幕：把一件物品变成很多件01物品
1、原来：
| 2 | 3 | 13 |
2、拆分后：
（1）第一组：
1件
重量：
2×1=2
价值：
3×1=3
（2）第二组：
2件
重量：
2×2=4
价值：
3×2=6
（3）第三组：
4件
重量：
2×4=8
价值：
3×4=12
（4）第四组：
6件
重量：
2×6=12
价值：
3×6=18
（5）得到：
| 2 | 3 |
| 4 | 6 |
| 8 | 12 |
| 12 | 18 |
3、神奇的事情发生了！
这些物品：
每个只能选一次
4、因此：
🌟多重背包
变成了
🌟01背包
第六幕：为什么正确？
1、很多同学第一次学到这里，都会怀疑：
这样不会丢失方案吗？
2、我们来验证。
拆分：
1
2
4
6
5、想拿：
5件
怎么办？
选：
1+4
6、想拿：
9件
选：
1+2+6
7、想拿：
13件
选：
1+2+4+6
8、所有数量：
0~13
全部都能表示！
不会漏！
第七幕：时间复杂度发生了什么？
1、原来：
1000件
需要：
枚举1000次
2、拆分后：
1
2
4
8
16
32
64
128
256
489
3、只有：
10组
左右。
4、为什么？
因为：
2¹⁰≈1024
5、于是：
时间复杂度从：
O(nms)
变成：
O(nm log s)
速度快速提升！
🚀🚀🚀
第八幕：标准拆分代码
1、假设：
w
2、重量
v
3、价值
s
4、数量
int k = 1;
while(k <= s)
{
W[++cnt] = k * w;
V[cnt] = k * v;
s -= k;
k *= 2;
}
if(s > 0)
{
W[++cnt] = s * w;
V[cnt] = s * v;
}
5、例如：
s=13
得到：
1
2
4
6
对应的新物品。
第九幕：接下来就是01背包
1、拆完以后。
直接使用01背包方法：
for(int i=1;i<=cnt;i++)
{
for(int j=m;j>=W[i];j–)
{
dp[j]
=
max(
dp[j],
dp[j-W[i]]+V[i]
);
}
}
2、因为：
已经变成：
每件只能选一次
3、所以：
倒序循环
第十幕：完整参考程序
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int W[10005];
int V[10005];
int cnt = 0;
for(int i=1;i<=n;i++)
{
int w,v,s;
cin>>w>>v>>s;
int k = 1;
while(k <= s)
{
W[++cnt] = k*w;
V[cnt] = k*v;
s -= k;
k *= 2;
}
if(s > 0)
{
W[++cnt] = s*w;
V[cnt] = s*v;
}
}
int dp[10005]={0};
for(int i=1;i<=cnt;i++)
{
for(int j=m;j>=W[i];j–)
{
dp[j]
=
max(
dp[j],
dp[j-W[i]]
+
V[i]
);
}
}
cout<<dp[m];
return 0;
}
第十一幕：三种背包统一了！
经过学习。
阿宝发现：
1、01背包
数量：
1
直接做。
2、完全背包
数量：
∞
正序。
3、多重背包
数量：
有限个
先拆分。
再变成01背包。
4、于是：
🌟背包三兄弟
| 01背包 | 1 |
| 完全背包 | 无限 |
| 多重背包 | 有限 |
🎯本课总结
1、核心思想
把：
有限个物品
拆成：
1
2
4
8
…
若干组。
2、拆分结果
例如：
13
拆成：
1
2
4
6
3、优化效果
原来：
O(nms)
现在：
O(nm log s)
4、重要结论
🌟
多重背包不好做，
二进制来帮忙。
拆成若干01包，
速度立刻变飞翔！
🏹课后挑战
1、有一种魔法药水：
| 3 | 5 | 11 |
2、请同学们：
① 用二进制优化拆分。
② 写出所有新物品的重量和价值。
③ 验证：
0~11瓶
是否都能表示出来。
3、如果你能够自己完成这道题
那么你已经掌握了信息学竞赛中，经典的优化技巧之一——二进制优化多重背包。🏆
