背包问题求方案数
题目 背包问题求方案数
思路分析
做这道题之前先写一下 数字组合
数字组合这题问的是所有方案数 就是简单的把原来集合的max属性变成了count属性
而这道题要我们求的是 最大价值的方案数
实际上就是把原本的01背包（求最大价值）和这个变形的01背包（求方案数）做一个结合
在同一dp过程中 同时把这两件事做了即可
思路
f[i][j]记录考虑前i件物品，当前背包容量为j时的最大价值。g[i][j]记录在考虑前i件物品，当前背包容量为j时，达到最大价值f[i][j]的方案数。
- 初始化：
f[0][0]不需要管 默认为0 从前0个物品中选体积不超过0的物品的总价值的最大值自然是0g[i][0] = 1无论考虑多少物品 总存在一种方案使得容量为0的背包达到价值0 即不选择任何物品 - 动态规划更新：
- 遍历物品
i从1到n，和背包容量j从0到m。 - 更新
f[i][j]：如果不取当前物品，则价值为f[i-1][j]；如果取当前物品（前提是j大于等于物品体积v[i]），则价值为f[i-1][j-v[i]] + w[i]，取两者的较大值。 - 更新
g[i][j]：- 如果
f[i][j]的值来源于f[i-1][j]（即不取当前物品），则方案数为g[i-1][j]。 - 如果
f[i][j]的值来源于f[i-1][j-v[i]] + w[i]（即取当前物品），则方案数为g[i-1][j-v[i]]。 - 注意，如果
f[i][j]同时满足上述两种情况，即f[i][j]的值既可以通过不取当前物品也可以通过取当前物品得到，那么g[i][j]应该累加这两种情况的方案数。
- 如果
- 最后，遍历
j从0到m，累加所有f[n][j]等于f[n][m]（即最大价值）时的g[n][j]值，得到的总和就是最终的方案数。
问题：
为什么累加所有f[n][j]等于f[n][m]（即最大价值）时的g[n][j]值，得到的总和就是最终的方案数？ 我们知道g[n][j]的含义是从前n个物品当中选 体积不超过j的所有达到最大价值的方案数 如果某个方案只选到了k(k是小于n的）就已经达到了最大价值f[n][m] 那它还需要表示为前n个物品中选吗 或者换句话说 所疑惑的这种情况 是否被包含进了g[n][0-m]当中？比如达到最大价值 此时只在k个物品中选了3 即g[k][3] 好像g[n][3]也包括了这个g[k][3]？
分析：
动态规划的状态定义和转移
在0-1背包问题中，状态f[i][j]表示考虑前i个物品，当前背包容量为j时的最大价值。状态g[i][j]记录的是达到这个最大价值的方案数。这里的重点是"考虑前i个物品"并不意味着必须选择第i个物品，也不意味着必须恰好选i个物品。它意味着在前i个物品中进行选择，不超过容量j的条件下可以达到的最大价值及其方案数。
考虑不同数量的物品
当我们说g[n][j]包括了g[k][3]（对于某个k < n和某个容量3），实际上我们是在说：在计算g[n][j]时，我们考虑了所有从第1个物品到第n个物品的可能组合，其中包括了那些仅使用前k个物品达到某个价值的所有方案。
如何理解“考虑前n个物品”中包含了更少物品的情况
动态规划的过程是累积的。当我们在计算f[i][j]和g[i][j]的值时，我们是基于之前所有的计算结果来的。这意味着，如果存在一个最优的方案，它实际上只选取了前k个物品中的一部分，那么这个方案在计算f[k][x]和g[k][x]时已经被考虑过，并且它的价值和方案数被递推到了f[n][j]和g[n][j]。
这是因为，当我们从k递推到n时，如果后面的物品没有被选择（即它们不增加总价值），f和g的值仍然会保留那个最大价值和对应的方案数，因为我们在动态规划中是通过比较和选择最大值来更新状态的。
结论
因此，即使某个最优方案实际上只选择了前k个物品中的一些，这个方案仍然会被包含在最终的g[n][j]中，因为在递推过程中，我们考虑了所有可能的物品组合，包括那些在中途就已经达到最大价值的方案。这就是动态规划的美妙之处：它通过局部最优解的累积，最终得到全局最优解，并能够统计达到这个全局最优解的所有可能的方案数。
代码
现在对于f[][]和g[][]的理解应该有一些了吧
那么再考虑最后一个问题
f[n][m]毋庸置疑是最大答案 我们01背包取最大价值就是取它
根据前面的分析 f[n][0-m]显然就是其他选法的总价值 它对应的选法数量都在g[n][0-m]当中
那么只要发现f[n][j]里有和我们最大价值f[n][m]相等的值 就把那些选法数量（g[n][j])累加起来
朴素：
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int v[N], w[N];
int f[N][N], g[N][N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
// 初始化方案数为1，即不选任何物品的情况
for (int i = 0; i <= n; i++)
g[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i-1][j]; // 不选第i个物品
g[i][j] = g[i-1][j]; // 继承不选的方案数
if (j >= v[i]) {
if (f[i][j] < f[i-1][j-v[i]] + w[i]) {
f[i][j] = f[i-1][j-v[i]] + w[i]; // 更新最大价值
g[i][j] = g[i-1][j-v[i]]; // 更新方案数
} else if (f[i][j] == f[i-1][j-v[i]] + w[i]) {
g[i][j] = (g[i][j] + g[i-1][j-v[i]]) % mod; // 累加方案数
}
}
}
}
int res = 0;
for (int j = 0; j <= m; j++) {
if (f[n][j] == f[n][m]){
res = (res + g[n][j]) % mod;
}
}
cout << res;
return 0;
}
接着就是老套路 消掉一维
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int v[N], w[N];
int f[N], g[N];
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
g[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
if (f[j] < f[j-v[i]] + w[i]) {
f[j] = f[j-v[i]] + w[i]; // 更新最大价值
g[j] = g[j-v[i]]; // 更新方案数
} else if (f[j] == f[j-v[i]] + w[i]) {
g[j] = (g[j] + g[j-v[i]]) % mod; // 累加方案数
}
}
}
int res = 0;
for (int j = 0; j <= m; j++) {
if (f[j] == f[m]){
res = (res + g[j]) % mod;
}
}
cout << res;
return 0;
}
我的这种理解方式是和y总以及其他题解不太一样的 但是和铅笔哥是差不多思路
感觉要比什么更改状态从不超过j变为恰好等于j要容易理解些
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int v[N],w[N];
int f[N][N],g[N][N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
for(int i=0;i<=n;i++)
g[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
g[i][j]=g[i-1][j];
if(v[i]<=j){
if(f[i][j]<f[i-1][j-v[i]]+w[i]){
f[i][j]=f[i-1][j-v[i]]+w[i];
g[i][j]=g[i-1][j-v[i]];
}
else if(f[i][j]==f[i-1][j-v[i]]+w[i])
g[i][j]=(g[i][j]+g[i-1][j-v[i]])%mod;
}
}
}
int res=0;
for(int j=0;j<=m;j++)
if(f[n][j]==f[n][m])
res=(res+g[n][j])%mod;
cout<<res;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;
int v[N],w[N];
int f[N],g[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i]>>w[i];
g[0]=1;
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
if(f[j]<f[j-v[i]]+w[i]){
f[j]=f[j-v[i]]+w[i];
g[j]=g[j-v[i]];
}
else if(f[j]==f[j-v[i]]+w[i])
g[j]=(g[j]+g[j-v[i]])%mod;
}
}
int res=0;
for(int j=0;j<=m;j++)
if(f[j]==f[m])
res=(res+g[j])%mod;
cout<<res;
return 0;
}
同类题型
视频讲解
⬅️ 背包问题求具体方案数 🏠 00-刷题理模型 ➡️ 跳台阶
💬 评论