01背包之前没理解透的一个细节
状态f[i][j]如果表示“前i件物品恰放入一个容量为v的背包可以获得的最大价值”,那么它实际上是可能不存在的,这时候最优解不一定是f[n][m],需要遍历背包大小。初始化状态数组时只将背包容量为0的值初始化为0,其他状态初始化为-INF表示不存在,保证递推过程中每一项都是实际存在的。
状态定义去掉恰,那么f[n][m]就是最优解,这儿状态转移时隐含了一层递推关系,即f[i][j] = max(f[i][j - 1], f[i][j])
,所以代码实现上可以省略掉最后遍历背包大小的一步。(初始化时所有背包容量的状态值都初始化为0)
f[i][j - 1] = max(f[i - 1][j - 1], f[i - 1][j - 1 - v[i] + w[i])
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] + w[i])
假设``f[i][j - 1]就是全局最优解,那么
f[i][j]```一定大于等于它吗?yes
假设f[i][j - 1] = f[0][0] + wx + wy + wz,观察状态转移方程,可以发现f[i][j] = f[0][1] wx + wy + wz + …, f[i][j] >= f[i][j - 1]