最近在补全提高课所有题目的题解,宣传一下汇总的地方提高课题解补全计划
题目描述
有 N 件 物品 和一个 容量 为 V 的背包。每件 物品 只能使用 一次
第 i 件 物品 的 体积 是 vi,价值 是 wi
求解将哪些物品装入背包,可使 总体积 不超过 V 的情况下, 总价值 最大
输出 最优选法的方案数 。答案可能很大,输出答案模 109+7 的结果
分析
本题是 背包DP 中的经典题型 —— 【背包DP求最优方案总数】
01背包求最优方案 具体都在这篇博客中 AcWing 423. 采药【01背包DP模型+朴素优化】
本题解主要描述如何求 最优方案总数
在这篇 AcWing 1013. 机器分配【分组背包+背包DP输出方案—拓扑图分析】 有对 DP—拓扑图 的描述
本题我们也可以利用这个 状态转移拓扑图 找出所有 最优解 的 状态转移路径,从而求解出方案数
闫氏DP分析法
01背包模型 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
不一样,二维代码是
if (maxv == f[i-1][j]) g[i][j] = g[i-1][j] % mod; if (maxv == f[i-1][j-v]+w) g[i][j] = (g[i][j] + g[i-1][j-v]) % mod;
如果直接优化成一维,如果只走下面的循环,相当于
g[i][j] = (g[i-1][j] + g[i-1][j-v]) % mod;
而如果只走下面的循环是不可以将两种情况加在一起的。
赞赞
y总那个为什么要初始化
都需要初始化的
它说的memset
膜拜orz
code 3 由于状态表示定义为恰好,所以要找价值最大这必须遍历dp数组。
想问下。第一种朴素做法(f,g为二维数组),可以把 g 和 f 写进一个循环里吗?我写进一个循环,发现g的值都是0
大佬可以把完善一下题解吗,把第一种朴素f,g同时判断写进做法给加上吗?
#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]; g[0][0] = 1; 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]); 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; }
铅笔佬%%%%%%%%%
彩铅哥,我想知道为啥定义成恰好为j的时候,二维的代码过不掉
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010, mod = 1e9 + 7; int n, m; int f[N][N], g[N][N]; int main() { cin >> n >> m; memset(f, -0x3f, sizeof f); f[0][0] = 0; for (int i = 0; i <= m; i ++ ) g[i][0] = 1; for (int i = 1; i <= n; i ++ ) { int v, w; cin >> v >> w; for (int j = 0; j <= m; j ++ ) { int maxv = f[i - 1][j]; int cnt = g[i - 1][j]; if (j >= v) { maxv = max(maxv, f[i - 1][j - v] + w); if (f[i - 1][j] == f[i - 1][j - v] + w) cnt += g[i - 1][j - v]; else if (maxv == f[i - 1][j - v] + w) cnt = g[i - 1][j - v]; } g[i][j] = cnt % mod; f[i][j] = maxv; } } int res = 0; for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i]); int cnt = 0; for (int i = 1; i <= n; i ++ ) for (int j = 0; j <= m; j ++ ) if (f[i][j] == res) cnt = (cnt + g[i][j]) % mod; cout << cnt << endl; return 0; }
统计 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