[笔记] 0-1背包问题的 DP 状态转移方程与 Bellman 方程转换

DP 状态转移方程

设 表示考虑前 个物品，当前背包剩余容量为 时，所能获得的最大价值； 和 分别为第 个物品的重量和价值。

则状态转移方程为：

对应术语

DP术语	对应RL术语
状态	，即“考虑第 i 个物品，剩余容量 c”
动作	：是否选第 i 个物品
奖励
状态转移
（状态）价值函数

从 DP 状态转移方程到 Bellman 方程

1. DP 状态转移方程

2. 代换为 RL 术语

进一步整理得：

这与 Bellman 方程的形式相同（）：