最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划
题目描述
有 $N$ 件 物品 和一个 容量 为 $V$ 的背包。每件 物品 只能使用 一次
第 $i$ 件 物品 的 体积 是 $v_i$，价值 是 $w_i$
求解将哪些物品装入背包，可使 总体积 不超过 $V$ 的情况下， 总价值 最大
输出 最优选法的方案数 。答案可能很大，输出答案模 $10^9+7$ 的结果
分析
本题是 背包DP 中的经典题型 —— 【背包DP求最优方案总数】
01背包求最优方案 具体都在这篇博客中 AcWing 423. 采药【01背包DP模型+朴素优化】
本题解主要描述如何求 最优方案总数
在这篇 AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】 有对 DP—拓扑图 的描述
本题我们也可以利用这个 状态转移拓扑图 找出所有 最优解 的 状态转移路径，从而求解出方案数
闫氏DP分析法
01背包模型 $\mathrm{f[i][j]}$
状态表示$f(i,j)$—集合： 考虑前 i 个物品，且当前已使用体积不超过 j 的方案
状态表示$f(i,j)$—属性： 该方案的价值为最大值 $\max$
状态转移$f(i,j)$： $f(i,j) = \begin{cases} 不选第i个物品： &\max\{f(i-1,j)\} \\\ 选第i个物品：&\max\{f(i-1,j - v_i) + w_i\} \end{cases}$
路径跟踪 $\mathrm{g[i][j]}$
状态表示$g(i,j)$—集合： 考虑前 i 个物品，当前已使用体积恰好是 j 的，且 价值 为最大的方案
状态表示$g(i,j)$—属性： 方案的数量 $Sum$
状态转移$g(i,j)$：
如果$f_{i,j}=f_{i-1,j}$ 且 $f_{i,j}=f_{i-1,j-v}+w$ 则 $g_{i,j} = g_{i-1,j} + g_{i-1,j-v}$
如果$f_{i,j}=f_{i-1,j}$ 且 $f_{i,j}\ne f_{i-1,j-v}+w$ 则 $g_{i,j} = g_{i-1,j}$
如果$f_{i,j}\ne f_{i-1,j}$ 且 $f_{i,j}=f_{i-1,j-v}+w$ 则 $g_{i,j} = g_{i-1,j-v}$
初始状态：g[0][0] = 1
Code(朴素写法)
时间复杂度： $O(N\times V)$
空间复杂度： $O(N\times V)$
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int w[N], v[N];
int f[N][N], g[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
for (int i = 1; i <= n; ++ i)
{
for (int j = 0; j <= m; ++ j)
{
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
g[0][0] = 1;
for (int i = 1; i <= n; ++ i)
{
for (int j = 0; j <= m; ++ j)
{
if (f[i][j] == f[i - 1][j])
g[i][j] = (g[i][j] + g[i - 1][j]) % mod;
if (j >= v[i] && 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 << endl;
return 0;
}
Code(朴素优化)
可以把 g 和 f 写进一个循环里，再判断 f 的 转移路径 的同时用 g 跟踪 转移路径
然后再用 01背包 的 朴素优化，把第一维消掉即可
时间复杂度： $O(N\times V)$
空间复杂度： $O(V)$
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, m;
int w[N], v[N];
int f[N], g[N];
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)
{
int temp = max(f[j], f[j - v[i]] + w[i]), c = 0;
if (temp == f[j]) c = (c + g[j]) % mod;
if (temp == f[j - v[i]] + w[i]) c = (c + g[j - v[i]]) % mod;
f[j] = temp, g[j] = c;
}
}
int res = 0;
for (int j = 0; j <= m; ++ j)
{
if (f[j] == f[m])
{
res = (res + g[j]) % mod;
}
}
cout << res << endl;
return 0;
}
走遍每一个铅笔哥的题解
醒醒你火了
想请教下，为什么f[i[[j]不定义成恰好，按道理来说，f[i][j]定义为不超过的情况下，那么最后求答案的时候g[i][j]不是会重复吗
大哥你会了不，我就是这纠结了半天
定义不超过的话 直接输出 不需要扫一遍了
定义不超过的话 直接输出 还方便点
这个题解把f作为不超过 个g[m]看做恰好 反而麻烦
xd，这个解释可以举个例子吗?看不太懂谢谢了
这里没有对f进行memset，具体情况可以看一下这位dalao的分享
https://www.acwing.com/file_system/file/content/whole/index/content/1306630/
带佬，你这个g[i][j]为什么不是恰好为j的方案数啊，如果是不大于j方案数的话不是应该直接输出g[m]就行了吗
对的，这里是个小错误，因为
g[i][j]的初始状态也只有一个g[0][0] = 1所以
g[i][j]的状态定义是恰好谢谢指出，已更正
f[i][j]也应该定义成恰好吧，数据有点弱，当成小于等于也能过
问一下一维背包那里，为什么我不定义中间变量c，直接拿g[j]来计算并赋值，maxv与两种状态都相等的情况也考虑了，但只能通过四个样例，不知道漏了哪一步和为什么要加上这个中间变量c
不一样，二维代码是
如果直接优化成一维，如果只走下面的循环，相当于
而如果只走下面的循环是不可以将两种情况加在一起的。
赞赞
y总那个为什么要初始化
都需要初始化的
它说的memset
膜拜orz
code 3 由于状态表示定义为恰好，所以要找价值最大这必须遍历dp数组。
想问下。第一种朴素做法（f,g为二维数组），可以把 g 和 f 写进一个循环里吗？我写进一个循环，发现g的值都是0
大佬可以把完善一下题解吗，把第一种朴素f,g同时判断写进做法给加上吗？
铅笔佬%%%%%%%%%
彩铅哥，我想知道为啥定义成恰好为j的时候，二维的代码过不掉
统计 $g$ 的目标状态那里错了，$g$ 的目标状态应该是 $g_{n,j}\quad (0\le j \le m)$
改了之后AC了，是不是因为 $g[i][j]$ 会重复计算某些最优解，而只需要枚举 $g[n][j]$ 就可以保证不重不漏地把最优解的数量统计出来？
emmm，这个是和 $g_{i,j}$ 的状态定义有关，你可以看一下上面题解的部分hh
应该跟你说的差不多是一个意思
哈哈，明白了，感谢聚聚耐心解答^_^
写得很详细了
谢谢支持hh
大佬，请问一下考虑状态时候考虑恰好和考虑不大于的差异体现在哪里。感觉无论从代码上还是从分析上都没有差异…?
和初始状态有关，不大于的话所有体积都可以作为初始状态
恰好的话，只有一个初始状态，那就是 f[0][0]
噢噢，所以说只在初始状态上有差异对吧，其他的我都写了一下感觉代码是一样的诶…
### 感谢
彩铅题解写真好❥
谢谢hh