dp

0-1背包

  • 至多装capacity，求方案数/最大价值和

  • 恰好装capacity，求方案数/最大/最小价值和

  • 至少装capacity，求方案数/最小价值和

可以获得状态转移方程：

1
2
dfs(i,c) = max(dfs(i-1,c), dfs(i-1,c-w[i]) + v[i])
dfs(i,c) = dfs(i-1,c)+dfs(i-1,c-w[i])

目标和

通过转换就可以得到0-1背包的一种，即求恰好时的方案数

记忆化搜索可以1：1地翻译成递推

1
2
3
f[i][c] = f[i-1][c] + f[i-1][c-w[i]]
// 为了避免负数
f[i+1][c] = f[i][c] + f[i][c-w[i]]

倘若空间优化成一个数组

1
2
3
4
f[c] = f[c] + f[c-w[i]]
/*
这里从左→右计算，考虑到 f[c-w[j]]可能已经覆盖成f[i+1][c-w[i]]，而不是一开始的f[i][c-w[i]]，因此从右→左计算
*

完全背包（可以重复选）

1
2
3
4
f[i+1][c] = min(f[i][c], f[i+1][c-w[i]]+v[i])
// 优化空间
f[c] = min(f[c], f[c-w[i]]+v[i])
// 这时候就要从左→右计算了

[!NOTE]

总结一下上面空间的优化的两种情况：

  • 当f[c-w[i]]是f[i+1]的时，即我们需要往前获最新的元素，左👉右
  • 当f[c-w[i]]是f[i]的时，即我们需要往前获取之前的元素，左👈右