01背包问题：从贪心到动态规划的优化

01背包问题：从贪心到动态规划的优化

背包问题是一个经典的优化问题，可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。01背包问题的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在01背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。

思路一、贪心算法

假设你有一个背包，容量为M。你现在有N件物品，每件物品质量为wi，价值是vi，每件物品只能放一次，求你放入背包的物品的价值最大是多少？

最容易想到的思路是贪心，也就是计算每一件物品的性价比（v/w），优先找性价比最高的装入包中。例如：

M=10，N=4

10 4 2 1 3 3 4 5 7 9

根据性价比来选择物品，首先选择性价比最高的7，然后是3和5，最后是9。这样得到的总价值是23。然而，这个方法并不总是正确的。例如：

M=10，N=4

10 3 7 14 6 11 4 7

质量为7的物品性价比最高，但如果把6和4的两个物品加在一起，11+7>14。因此，贪心算法在这个例子中并不适用。

思路二、动态规划（二维）

我们用f表示前i件物品放入容量为j的背包中可以获得的最大价值。在01背包中，每种物品只有两种选择：选与不选。

Case 1：不选。那么f=f，和上一个一样。

Case 2：选。那么此时背包的容量就减少了w，背包剩余j-w的空间，f=f+v。

“将前i件物品放入容量为j的背包中”这个子问题，若只考虑第i件物品的策略，就可以转化为一个只和前i-1件物品相关的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，价值为f；如果放第i件物品，那么问题就转化为“前i−1件物品放入剩下的容量为j−Wi的背包中”，此时能获得的最大价值就是f再加上通过放入第i件物品获得的价值Vi。

思路三、优化（一维）

可以看出，f的状态和f相关，那么能否优化为一维数组？如果单纯去掉主循环和i相关的部分，会发现不对，f的状态就由f推导了，而之前的j循环中，已经改变了f的值，这是明显错误的。有没有解决方法呢？仔细一想，会发现动态规划的优化需要一些技巧和数学推导。