01 背包是一种动态规划问题。动态规划的核心就是状态转移方程,本文主要解释 01 背包状态转移方程的原理。 问题描述 01 背包问题可描述为如下问题: 有一个容量为 V 的背包,还有 n 个物体。现在忽略物体实际几何形状,我们认为只要背包的剩余容量大于等于物体体积,那就可以装进背包里。每个物体都有两个属性,即体积 w 和价值 v。 问:如何向背包装物体才能使背包中物体的总价值最大? 原始的 01 背包 01 背包的状态转移方程为 C_{[i][j]} = \max(C_{[i - 1][j]}, C_{[i - 1…