动态规格经典问题
现在我有一只背包和N个物品，如果物品很多，不能全部塞进背包里。相信很多人的选择是，把最有价值的物品尽可能多地往背包里塞。
问题描述：
给定N个物品和一个背包。物品i的重量是Wi，其价值为vi，背包的容量为C。问应该如何选择装入背包的物品，使得装入背包的物品的总价值为最大？
在选择物品的时候，对每种物品i，只有两种选择，即装入背包或不装入背包。同一物品i不能装入多次，也不能只装入物品的一部分。因此，该问题被称为0-1背包问题。
图1 N个物品的重量和价值
问题分析：
设V(i,j)表示在前i(1≤i≤N)个物品中能够装入容量为j(1≤j≤C)的背包中的物品的最大价值，得到以下的函数：
(1) V(i,0) = V(0,j) = 0
(2) V(i,j) = V(i - 1,j) (当j ＜ Wi)
(3) V(i,j) = max{V(i - 1,j), V(i - 1,j - Wi) + vi) } (当j ≥ Wi)
其中
(2)式表明：如果第i个物品的重量大于背包的容量，物品i不能装入背包，则装入前i个物品得到的最大价值和装入前i - 1个物品得到的最大价是相同的；
(3)式表明：如果第i个物品的重量小于背包的容量，分以下两种情况：
(a)如果把第i个物品装入背包，则先预留物品i的重量，再计算剩余重量里i - 1个物品能装入物品的最大价值，则背包物品的价值等于第i - 1个物品装入容量位j - Wi 的背包中的最大价值加上第i个物品的价值vi；
(b)如果不把第i个物品装入背包，则背包中物品价值就等于把前i - 1个物品装入容量为j的背包中所取得的价值。
显然，取二者中价值最大的值作为把前i个物品装入容量为j的背包中的最优解。
使用动态规划求解时，我们建立这样的一张二维表，来表示前i个物品在背包容量为j时，背包能装入物品的最大价值。例如现在背包的容量C为10。
图二 最大价值表
在构建出来的二维表中，右下角V(N,C)的值就是问题的解。
当然，现在只能算出N个物品放进C容量的背包时，能放入最大价值的值，如需知道具体挑选的是哪些物品，还要做一些辅助计算。这里暂时不作讨论。