动态规划公式合集-背包问题
作者:
白墙
,
2021-08-23 15:37:03
,
所有人可见
,
阅读 316
426. 开心的金明
f[i][j] = max{f[i - 1][j - v] + v * w};
10. 有依赖的背包问题
f[root][m]表示以root为根,选择总体积不超过m的最大价值
先从下到上处理了选择每个结点的值
for (int i = m; i >= v[i]; i --) f[u][i] = f[u][i - v[i]] + w[u];
然后在循环里对于每个儿子结点
for (int i = m - v[u]; i >= 0; i --)
for (int j = 0; j <= i; j ++)
f[u][i] = max (f[u][j], f[son][l] + f[u][i - l]);
11. 背包问题求方案数
f[j]表示体积正好为j的最大价值
g[j]表示体积正好为j的方案数
对于f[j]我们按照01背包的方法求
g[j]要根据对于当前物选择或者不选择的最大价值来判断。如果两种情况相等,那么就需要
g[j] = (g[j] + g[j - v]) % M;
否则g[j]取最大价值的一方
12. 背包问题求具体方案
通过将目标设置为f[1][m]然后利用公式求每个位置选择背包
487. 金明的预算方案
通过pair,vector<pair>存,因为这里是个森林。
然后通过二进制枚举