问题: 有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 Ci ,得到的价值是 W i 。求解将哪些物品装入背包可使价值总和最大。 解题思路: 其实一开始看这题,会让人有些不知所措,不过,这题是有规律可寻的。此题的特点是:每种物品仅有一件,可以选择放或不放。用子问题定义状态:即 F [i, v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是 F [i, v] = max {F [i − 1, v], F [i − 1, v − Ci ] + Wi } 对这个方程的解释如下: 将前 i 件物品放入容量为 v 的背包中”这个子问题,若...