0-1背包问题¶
问题描述：有N个物品，物品i的重量为$w_i$，价值为$v_i$。有一个背包，能装入的最大重量为W。求将哪些物品放入背包使得背包内的价值最大。
解题思路：0-1背包问题中，每个物品有两种选择，放入背包或者不放入背包。另一种说法，每个物品只能选0个或1个。 考虑第N个物品，只有两种情况，放入背包和不放入背包。 当放入背包，背包剩余容量$W-w_N$。那么我们需要求一个子问题：前N-1个物品放入容量为$W-w_N$的背包能得到的最大价值。加上物品N的价值，即为这种情况得到的最大价值。 当不放入背包，那么我们需要求解子问题：前N-1个物品放入容量为W的背包能得到的最大价值。 比较这两种情况，价值大的即为最终的结果。
状态转移方程：有了上面的分析。我们令F[i,w]表示前i个物品，放入容量为w的背包能得到的最大价值。有状态转移方程：
Written with StackEdit.