第七课《背包里的数学魔法——方案数背包》故事开始宝藏猎人的新任务经过前面的学习阿宝已经学会了✅ 01背包求最大价值✅ 完全背包求最大价值✅ 多重背包求最大价值✅ 分组背包求最大价值1、阿宝发现以前所有背包题都在问能获得多少价值或者最大价值是多少2、例如宝物重量价值金币23钻石35问最大价值是多少3、这种题目DP数组里存的是最大价值4、可是有一天。国王又出了一个奇怪的问题。5、国王的问题(1) 仓库里有宝物重量红宝石1蓝宝石2绿宝石3背包容量4(2) 国王问阿宝容量恰好装满4一共有多少种装法6、阿宝愣住了。因为这次不是问价值最大是多少而是问有多少种方案方案数背包登场第一幕什么叫方案数1、先看例子。1宝石编号重量1122332容量42、看看有哪些装法。方案11 3重量134成功方案2只有4重量的宝石没有方案32 2不行因为每个宝石只有一个。3、所以只有13这一种。答案1第二幕DP存什么1、以前dp[j]表示最大价值2、现在dp[j]表示凑出重量j的方法数3、注意这里发生了巨大变化。4、以前存价值dp[j]100意思最大价值1005、现在存方案数dp[j]100意思有100种方法第三幕最重要的初始化1、这里最容易错2、先问大家凑出重量0有多少种方法3、很多同学说0种❌4、其实什么都不选就是一种方法5、所以dp[0]1;这是方案数背包的基础6、记住dp[0]1表示空方案第四幕状态转移1、还是01背包的方法。1宝石w[i]2如果当前重量j3选这个宝石会从哪里转移来4当然是j-w[i]2、例如重量3的宝石。想凑出5那么之前必须先凑出23、因此dp[5] dp[2]4、方案数转移dp[j] dp[j-w[i]]5、注意不是max()了因为方案数要累加。第五幕手算例子1、宝石重量1232、容量43、初始化dp[0]14、数组重量01234初始100005、处理重量1倒序for(j4;j1;j--)更新dp[1]dp[0]得到重量01234状态110006、处理重量2更新dp[3]dp[1]得到1更新dp[2]dp[0]得到1数组重量01234状态111107、处理重量3更新dp[4]dp[1]因为dp[1]1所以dp[4]18、最终重量01234状态11121答案dp[4] 1只有一种方案13第六幕为什么是加法1、以前最大价值只能保留最大的所以是max()2、现在方案数每种方法都算。例如凑出4的方法。方法A13方法B22如果允许的话总方案数2因此 第七幕完整代码01背包方案数1、输入物品数 容量 每个物品重量2、例如3 4 1 2 33、程序#include iostream using namespace std; int main() { int n,m; cinnm; int w[105]; for(int i1;in;i) { cinw[i]; } long long dp[10005]{0}; dp[0]1; for(int i1;in;i) { for(int jm;jw[i];j--) { dp[j] dp[j-w[i]]; } } coutdp[m]endl; return 0; }第八幕完全背包方案数1、如果物品无限使用呢例如硬币1元 2元无限个问组成4元有多少种方法2、这时转移仍然是dp[j] dp[j-w]3、区别只有一个正序循环for(jw;jm;j)因为完全背包允许重复使用。第九幕背包家族大集合类型求什么转移01背包最大价值max完全背包最大价值max多重背包最大价值max分组背包最大价值max方案数背包方案数量发现了吗1、前面max()家族2、现在家族第十幕方案数背包的经典应用生活中非常常见。1、硬币问题1元2元5元组成10元多少种方案2、选课问题课程学分2 3 4凑满10学分多少种选法3、糖果问题不同糖果重量。装满袋子多少种装法全部都是方案数背包本课总结1、状态定义dp[j]表示凑出重量j的方法数2、初始化最重要dp[0]1;表示空方案3、转移dp[j] dp[j-w[i]];不是max()是4、01方案数背包for(jm;jw[i];j--)倒序5、完全方案数背包for(jw[i];jm;j)正序6、终极口诀价值背包求最优 状态转移用max。 方案背包数方法 状态转移改加法。 dp[0]最为重要 空方案要记牢课后挑战1、有4块魔法石重量12342、背包容量53、请同学们① 求恰好装满5有多少种方案。② 画出完整DP数组变化过程。③ 找出每一种具体方案。当你能够自己列出所有方案并且能解释为什么程序得到同样的答案时你就真正掌握了方案数背包的核心思想✨
GESP6级C++考试语法知识（五十四、动态规划----背包问题（七、方案数背包）
发布时间：2026/6/8 18:11:08
第七课《背包里的数学魔法——方案数背包》故事开始宝藏猎人的新任务经过前面的学习阿宝已经学会了✅ 01背包求最大价值✅ 完全背包求最大价值✅ 多重背包求最大价值✅ 分组背包求最大价值1、阿宝发现以前所有背包题都在问能获得多少价值或者最大价值是多少2、例如宝物重量价值金币23钻石35问最大价值是多少3、这种题目DP数组里存的是最大价值4、可是有一天。国王又出了一个奇怪的问题。5、国王的问题(1) 仓库里有宝物重量红宝石1蓝宝石2绿宝石3背包容量4(2) 国王问阿宝容量恰好装满4一共有多少种装法6、阿宝愣住了。因为这次不是问价值最大是多少而是问有多少种方案方案数背包登场第一幕什么叫方案数1、先看例子。1宝石编号重量1122332容量42、看看有哪些装法。方案11 3重量134成功方案2只有4重量的宝石没有方案32 2不行因为每个宝石只有一个。3、所以只有13这一种。答案1第二幕DP存什么1、以前dp[j]表示最大价值2、现在dp[j]表示凑出重量j的方法数3、注意这里发生了巨大变化。4、以前存价值dp[j]100意思最大价值1005、现在存方案数dp[j]100意思有100种方法第三幕最重要的初始化1、这里最容易错2、先问大家凑出重量0有多少种方法3、很多同学说0种❌4、其实什么都不选就是一种方法5、所以dp[0]1;这是方案数背包的基础6、记住dp[0]1表示空方案第四幕状态转移1、还是01背包的方法。1宝石w[i]2如果当前重量j3选这个宝石会从哪里转移来4当然是j-w[i]2、例如重量3的宝石。想凑出5那么之前必须先凑出23、因此dp[5] dp[2]4、方案数转移dp[j] dp[j-w[i]]5、注意不是max()了因为方案数要累加。第五幕手算例子1、宝石重量1232、容量43、初始化dp[0]14、数组重量01234初始100005、处理重量1倒序for(j4;j1;j--)更新dp[1]dp[0]得到重量01234状态110006、处理重量2更新dp[3]dp[1]得到1更新dp[2]dp[0]得到1数组重量01234状态111107、处理重量3更新dp[4]dp[1]因为dp[1]1所以dp[4]18、最终重量01234状态11121答案dp[4] 1只有一种方案13第六幕为什么是加法1、以前最大价值只能保留最大的所以是max()2、现在方案数每种方法都算。例如凑出4的方法。方法A13方法B22如果允许的话总方案数2因此 第七幕完整代码01背包方案数1、输入物品数 容量 每个物品重量2、例如3 4 1 2 33、程序#include iostream using namespace std; int main() { int n,m; cinnm; int w[105]; for(int i1;in;i) { cinw[i]; } long long dp[10005]{0}; dp[0]1; for(int i1;in;i) { for(int jm;jw[i];j--) { dp[j] dp[j-w[i]]; } } coutdp[m]endl; return 0; }第八幕完全背包方案数1、如果物品无限使用呢例如硬币1元 2元无限个问组成4元有多少种方法2、这时转移仍然是dp[j] dp[j-w]3、区别只有一个正序循环for(jw;jm;j)因为完全背包允许重复使用。第九幕背包家族大集合类型求什么转移01背包最大价值max完全背包最大价值max多重背包最大价值max分组背包最大价值max方案数背包方案数量发现了吗1、前面max()家族2、现在家族第十幕方案数背包的经典应用生活中非常常见。1、硬币问题1元2元5元组成10元多少种方案2、选课问题课程学分2 3 4凑满10学分多少种选法3、糖果问题不同糖果重量。装满袋子多少种装法全部都是方案数背包本课总结1、状态定义dp[j]表示凑出重量j的方法数2、初始化最重要dp[0]1;表示空方案3、转移dp[j] dp[j-w[i]];不是max()是4、01方案数背包for(jm;jw[i];j--)倒序5、完全方案数背包for(jw[i];jm;j)正序6、终极口诀价值背包求最优 状态转移用max。 方案背包数方法 状态转移改加法。 dp[0]最为重要 空方案要记牢课后挑战1、有4块魔法石重量12342、背包容量53、请同学们① 求恰好装满5有多少种方案。② 画出完整DP数组变化过程。③ 找出每一种具体方案。当你能够自己列出所有方案并且能解释为什么程序得到同样的答案时你就真正掌握了方案数背包的核心思想✨
