GESP6级C++考试语法知识（五十四、动态规划----背包问题（七、方案数背包）

第七课《背包里的数学魔法——方案数背包》

🎒故事开始：宝藏猎人的新任务

经过前面的学习，阿宝已经学会了：

✅ 01背包

求最大价值

✅ 完全背包

求最大价值

✅ 多重背包

求最大价值

✅ 分组背包

求最大价值

1、阿宝发现：

以前所有背包题都在问：

能获得多少价值？

或者：

最大价值是多少？

2、例如：

问：

最大价值是多少？

3、这种题目，

DP数组里存的是：

最大价值

4、可是有一天。

国王又出了一个奇怪的问题。

5、👑国王的问题

(1) 仓库里有：

背包容量：

4

(2) 国王问：

阿宝！

容量恰好装满4，

一共有多少种装法？

6、阿宝愣住了。

因为这次：

不是问：

价值最大是多少

而是问：

有多少种方案

🌟方案数背包登场

第一幕：什么叫方案数？

1、先看例子。

（1）宝石：

（2）容量：

4

2、看看有哪些装法。

方案1：

1 + 3

重量：

1+3=4

成功

方案2：

只有4重量的宝石？

没有

方案3：

2 + 2

不行

因为每个宝石只有一个。

3、所以：

只有

1+3

这一种。

答案：

1

第二幕：DP存什么？

1、以前：

dp[j]

表示：

最大价值

2、现在：

dp[j]

表示：

凑出重量j的方法数

3、注意！

这里发生了巨大变化。

4、🌟以前存价值

dp[j]=100

意思：

最大价值100

5、🌟现在存方案数

dp[j]=100

意思：

有100种方法

第三幕：最重要的初始化

1、这里最容易错！

2、先问大家：

凑出重量0

有多少种方法？

3、很多同学说：

0种

❌

4、其实：

什么都不选

就是一种方法！

5、所以：

dp[0]=1;

这是方案数背包的基础！

6、🌟记住

dp[0]=1

表示：

空方案

第四幕：状态转移

1、还是01背包的方法。

（1）宝石：

w[i]

（2）如果当前重量：

j

（3）选这个宝石：

会从哪里转移来？

（4）当然是：

j-w[i]

2、例如：

重量3的宝石。

想凑出：

5

那么之前必须先凑出：

2

3、因此：

dp[5] += dp[2]

4、🌟方案数转移

dp[j] += dp[j-w[i]]

5、注意不是：

max()

了！

因为：

方案数要累加。

第五幕：手算例子

1、宝石：

2、容量：

4

3、初始化：

dp[0]=1

4、数组：

5、处理重量1

倒序：

for(j=4;j>=1;j--)

更新：

dp[1]+=dp[0]

得到：

6、处理重量2

更新：

dp[3]+=dp[1]

得到：

1

更新：

dp[2]+=dp[0]

得到：

1

数组：

7、处理重量3

更新：

dp[4]+=dp[1]

因为：

dp[1]=1

所以：

dp[4]=1

8、最终：

答案：

dp[4] = 1

只有一种方案：

1+3

第六幕：为什么是加法？

1、以前：

最大价值

只能保留：

最大的

所以是：

max()

2、现在：

方案数

每种方法都算。

例如：

凑出4的方法。

方法A：

1+3

方法B：

2+2

（如果允许的话）

总方案数：

2

因此：

+ =

第七幕：完整代码（01背包方案数）

1、输入：

物品数 容量 每个物品重量

2、例如：

3 4 1 2 3

3、程序：

#include <iostream> using namespace std; int main() { int n,m; cin>>n>>m; int w[105]; for(int i=1;i<=n;i++) { cin>>w[i]; } long long dp[10005]={0}; dp[0]=1; for(int i=1;i<=n;i++) { for(int j=m;j>=w[i];j--) { dp[j] += dp[j-w[i]]; } } cout<<dp[m]<<endl; return 0; }

第八幕：完全背包方案数

1、如果物品无限使用呢？

例如：

硬币：

1元 2元

无限个

问：

组成4元有多少种方法？

2、这时：

转移仍然是：

dp[j] += dp[j-w]

3、区别只有一个：

正序循环

for(j=w;j<=m;j++)

因为：

完全背包允许重复使用。

第九幕：背包家族大集合

发现了吗？

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(j=m;j>=w[i];j--)

倒序

5、完全方案数背包

for(j=w[i];j<=m;j++)

正序

6、🌟终极口诀

价值背包求最优， 状态转移用max。 方案背包数方法， 状态转移改加法。 dp[0]最为重要， 空方案要记牢！

🏹课后挑战

1、有4块魔法石：

2、背包容量：

5

3、请同学们：

① 求恰好装满5有多少种方案。

② 画出完整DP数组变化过程。

③ 找出每一种具体方案。

当你能够自己列出所有方案，并且能解释为什么程序得到同样的答案时，你就真正掌握了方案数背包的核心思想！🏆✨