第四课《军火库管理大师——多重背包》故事开始皇家军火库1、经过前面的学习阿宝已经掌握了✅ 01背包每件物品只能拿一次✅ 完全背包每件物品可以无限拿2、这一天国王又交给阿宝一个任务皇家军火库要搬迁请你帮忙把武器装进运输车3、阿宝来到军火库。仓库管理员拿出清单武器重量价值数量宝剑233把盾牌342个4、阿宝一看就懵了咦这不是01背包也不是完全背包5、因为1宝剑有3把可以拿0把 1把 2把 3把2盾牌有2个可以拿0个 1个 2个3既不是只能拿1次4也不是无限拿6、这就是今天的新主角多重背包Multiple Knapsack第一幕什么是多重背包1、先看三种背包的区别。101背包宝剑数量 1选择0把 1把2完全背包宝剑数量 ∞选择0把 1把 2把 3把 4把 ……3多重背包宝剑数量 3选择0把 1把 2把 3把2、总结多重背包每种物品有固定数量上限第二幕军火运输任务1、运输车容量102、武器编号重量价值数量123323423、问最大价值是多少第三幕先思考状态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 数量 32、对于容量 j可能1不拿0把2拿1把重量2 价值33拿2把重量4 价值64拿3把重量6 价值95全部都要尝试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] ≤ j5、核心代码for(k0;ks[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、运输车容量52、只有一种武器重量价值数量2333、初始化i\j01234500000004、处理宝剑。1容量2尝试拿0把 价值0拿1把 价值3最大3所以dp[1][2]32容量4尝试0把 → 01把 → 32把 → 6最大6所以dp[1][4]63容量5尝试0把1把2把最多6得到i\j01234500000001003366第八幕为什么是三层循环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; cinnm; int w[105]; int v[105]; int s[105]; for(int i1;in;i) { cinw[i]v[i]s[i]; } int dp[105][1005]{0}; for(int i1;in;i) { for(int j0;jm;j) { for(int k0; ks[i] k*w[i]j; k) { dp[i][j] max( dp[i][j], dp[i-1][j-k*w[i]] k*v[i] ); } } } coutdp[n][m]; return 0; }第十幕时间复杂度1、有的同学会问这样做有没有问题有而且问题很大2、假设100种物品每种100件容量100003、那么100 × 10000 × 1001亿次4、非常慢第十一幕发现新的危机1、国王又来了。这次药水 1000瓶2、阿宝傻眼了。难道for(k0;k1000;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、三种背包对比类型数量01背包1完全背包无限多重背包有限个课后挑战1、运输车容量82、武器武器重量价值数量宝剑233盾牌3523、请同学们① 画出完整的 dp[i][j] 表。② 算出最终答案。③ 思考如果宝剑数量从 3 把变成 1000 把会发生什么下节课我们将学习如何把这 1000 把宝剑变成几个“分身宝剑”让程序速度瞬间提升
GESP6级C++考试语法知识（五十一、动态规划----背包问题（四、多重背包问题）
发布时间：2026/6/5 21:00:16
第四课《军火库管理大师——多重背包》故事开始皇家军火库1、经过前面的学习阿宝已经掌握了✅ 01背包每件物品只能拿一次✅ 完全背包每件物品可以无限拿2、这一天国王又交给阿宝一个任务皇家军火库要搬迁请你帮忙把武器装进运输车3、阿宝来到军火库。仓库管理员拿出清单武器重量价值数量宝剑233把盾牌342个4、阿宝一看就懵了咦这不是01背包也不是完全背包5、因为1宝剑有3把可以拿0把 1把 2把 3把2盾牌有2个可以拿0个 1个 2个3既不是只能拿1次4也不是无限拿6、这就是今天的新主角多重背包Multiple Knapsack第一幕什么是多重背包1、先看三种背包的区别。101背包宝剑数量 1选择0把 1把2完全背包宝剑数量 ∞选择0把 1把 2把 3把 4把 ……3多重背包宝剑数量 3选择0把 1把 2把 3把2、总结多重背包每种物品有固定数量上限第二幕军火运输任务1、运输车容量102、武器编号重量价值数量123323423、问最大价值是多少第三幕先思考状态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 数量 32、对于容量 j可能1不拿0把2拿1把重量2 价值33拿2把重量4 价值64拿3把重量6 价值95全部都要尝试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] ≤ j5、核心代码for(k0;ks[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、运输车容量52、只有一种武器重量价值数量2333、初始化i\j01234500000004、处理宝剑。1容量2尝试拿0把 价值0拿1把 价值3最大3所以dp[1][2]32容量4尝试0把 → 01把 → 32把 → 6最大6所以dp[1][4]63容量5尝试0把1把2把最多6得到i\j01234500000001003366第八幕为什么是三层循环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; cinnm; int w[105]; int v[105]; int s[105]; for(int i1;in;i) { cinw[i]v[i]s[i]; } int dp[105][1005]{0}; for(int i1;in;i) { for(int j0;jm;j) { for(int k0; ks[i] k*w[i]j; k) { dp[i][j] max( dp[i][j], dp[i-1][j-k*w[i]] k*v[i] ); } } } coutdp[n][m]; return 0; }第十幕时间复杂度1、有的同学会问这样做有没有问题有而且问题很大2、假设100种物品每种100件容量100003、那么100 × 10000 × 1001亿次4、非常慢第十一幕发现新的危机1、国王又来了。这次药水 1000瓶2、阿宝傻眼了。难道for(k0;k1000;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、三种背包对比类型数量01背包1完全背包无限多重背包有限个课后挑战1、运输车容量82、武器武器重量价值数量宝剑233盾牌3523、请同学们① 画出完整的 dp[i][j] 表。② 算出最终答案。③ 思考如果宝剑数量从 3 把变成 1000 把会发生什么下节课我们将学习如何把这 1000 把宝剑变成几个“分身宝剑”让程序速度瞬间提升
