企业官网建设流程全解析

第四课《军火库管理大师——多重背包》

🎒故事开始：皇家军火库

1、经过前面的学习，阿宝已经掌握了：

✅ 01背包

每件物品只能拿一次

✅ 完全背包

每件物品可以无限拿

2、这一天，国王又交给阿宝一个任务：

皇家军火库要搬迁！

请你帮忙把武器装进运输车！

3、阿宝来到军火库。

仓库管理员拿出清单：

4、阿宝一看就懵了：

咦？

这不是01背包！

也不是完全背包！

5、因为：

（1）宝剑有3把

可以拿：

0把 1把 2把 3把

（2）盾牌有2个

可以拿：

0个 1个 2个

（3）既不是：

只能拿1次

（4）也不是：

无限拿

6、这就是今天的新主角：

🌟多重背包（Multiple Knapsack）

第一幕：什么是多重背包？

1、先看三种背包的区别。

（1）01背包

宝剑：

数量 = 1

选择：

0把 1把

（2）完全背包

宝剑：

数量 = ∞

选择：

0把 1把 2把 3把 4把 ……

（3）多重背包

宝剑：

数量 = 3

选择：

0把 1把 2把 3把

2、🌟总结

多重背包：

每种物品有固定数量上限

第二幕：军火运输任务

1、运输车容量：

10

2、武器：

3、问：

最大价值是多少？

第三幕：先思考状态

1、仍然定义：

dp[i][j]

2、表示：

前 i 种物品

容量 j

最大价值

3、这和前面完全一样。

变化的是：

状态转移

第四幕：以前怎么转移？

1、01背包

（1）只有两种情况：

不选 选1次

（2）所以：

dp[i][j] = max( dp[i-1][j], dp[i-1][j-w]+v )

2、完全背包

无限选择

3、而多重背包呢？

第五幕：多重背包的核心思想

1、以宝剑为例：

重量 = 2 价值 = 3 数量 = 3

2、对于容量 j：

可能：

（1）不拿

0把

（2）拿1把

重量2 价值3

（3）拿2把

重量4 价值6

（4）拿3把

重量6 价值9

（5）全部都要尝试！

（6）于是：

🌟枚举件数

第六幕：状态转移公式

1、设：

s[i]

表示数量。

2、那么：

dp[i][j] = max( dp[i-1][j-k*w[i]] + k*v[i] )

3、其中：

k

表示拿了几件。

4、范围：

0 ≤ k ≤ s[i]

并且：

k*w[i] ≤ j

5、🌟核心代码

for(k=0;k<=s[i];k++) { if(k*w[i] <= j) { dp[i][j] = max( dp[i][j], dp[i-1][j-k*w[i]] + k*v[i] ); } }

第七幕：手算一个例子

1、运输车容量：

5

2、只有一种武器：

3、初始化：

4、处理宝剑。

（1）容量2

尝试：

拿0把 价值0

拿1把 价值3

最大：

3

所以：

dp[1][2]=3

（2）容量4

尝试：

0把 → 0

1把 → 3

2把 → 6

最大：

6

所以：

dp[1][4]=6

（3）容量5

尝试：

0把

1把

2把

最多：

6

得到：

第八幕：为什么是三层循环？

1、观察公式：

（1）第一层：

for(i)

枚举物品

（2）第二层：

for(j)

枚举容量

（3）第三层：

for(k)

枚举拿几件

2、完整结构：

for(i) { for(j) { for(k) { ... } } }

3、所以：

🌟三层循环DP

第九幕：参考程序

#include <iostream> #include <algorithm> using namespace std; int main() { int n,m; cin>>n>>m; int w[105]; int v[105]; int s[105]; for(int i=1;i<=n;i++) { cin>>w[i]>>v[i]>>s[i]; } int dp[105][1005]={0}; for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { for(int k=0; k<=s[i] && k*w[i]<=j; k++) { dp[i][j] = max( dp[i][j], dp[i-1][j-k*w[i]] + k*v[i] ); } } } cout<<dp[n][m]; return 0; }

第十幕：时间复杂度

1、有的同学会问：

这样做有没有问题？

有！

而且问题很大！

2、假设：

100种物品

每种：

100件

容量：

10000

3、那么：

100 × 10000 × 100

=

1亿次

4、非常慢！

第十一幕：发现新的危机

1、国王又来了。

这次：

药水 1000瓶

2、阿宝傻眼了。

难道：

for(k=0;k<=1000;k++)

？

3、这样太慢了！

4、于是魔法学院开始研究：

🌟二进制分身术

把：

1000个物品

拆成：

1 2 4 8 16 ...

这就是下一课要学习的：

⚔️《分身术卷轴——二进制优化》⚔️

🎯本课总结

1、多重背包定义

每种物品：

有固定数量上限

2、状态定义

dp[i][j]

前 i 种物品

容量 j

最大价值

3、核心思想

枚举拿几件

4、状态转移

dp[i][j] = max( dp[i-1][j-k*w[i]] + k*v[i] )

5、循环结构

for(i) { for(j) { for(k) { } } }

6、三种背包对比

🏹课后挑战

1、运输车容量：

8

2、武器：

3、请同学们：

① 画出完整的 dp[i][j] 表。

② 算出最终答案。

③ 思考：

如果宝剑数量从 3 把变成 1000 把，会发生什么？

下节课，我们将学习如何把这 1000 把宝剑变成几个“分身宝剑”，让程序速度瞬间提升！🚀