[AcWing算法基础课]动态规划之01背包

题目链接：01背包

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。

首先，我们应该找到“01背包”问题的一个特点就是每件物品只能使用一次。对于每一个物品，我们只需要考虑“选”或“不选”，这可能就是名字的来源吧。

“01背包”问题适合使用动态规划算法解决，也就是“记住求过的解来节省时间”。

下面先给出“01背包”问题的模板：

    // v[i]->体积  w[i]->价值 // f[i][j] 放入第i个物体,背包容量为j时的总价值for(int i = 1;i <= n;i++){  //动态规划for(int j = 0;j <= m;j++){if(v[i] <= j){f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);}}}int res = 0;  //最优解for(int j = 0;j <= m;j++){res = max(res,f[n][j]);}

接下来给大家举一个例子演示一下，方便大家理解。

我们假设有4个物品，并把每一个物品响应的体积和价值标注出来（下图的左侧），然后设置书包的体积为5。大家应该可以发现：

放入0个物品时，无论体积为多少，价值都为0。所以第一行全部填0。
当书包的体积为0时，不能放入任何物品，价值也都为0。所以第一列全部填0。

接下来看放入第1个物品会发生什么变化，也就是完善第二行。

便于理解的解释：第1个物品的体积为1，价值为2。当书包体积 j = 1时， j = v [ i ]，可以放入第1个物体，故此时书包的价值为2。当书包体积 j > 1时， j > v [ i ]，都可以放入第1个物体，故此时书包的价值仍然为2。第二行填完了。

基于代码的解释：当书包体积 j = 1时，我们考虑是否放入第1个物品：

不放入，那么书包的价值 f [1][1] 和 f [0][1]相同。（没放入任何物品，无论书包体积为多少，书包的价值都为0）。
放入，那么书包的价值 f [1][1] 就应该看放入第0个物品，书包的体积为1减去第1个物品的体积1时，书包的价值（1 - 1 = 0）。简单来说，现在书包的体积（j = 1）减去第1 个物品的体积（v [1] = 1）应该等于放入第0个物品时书包的体积（j - v [1] = 1 - 1 = 0）。只有放入第0个物体，书包体积为0时，我才能在书包体积为1时放入第1个物体，否则放不下。

对于这两种情况，我们应该选择最优的方法，也就是比较这两种方法的价值，取最大值。