0-1背包问题是一个基本问题，基于这个基本问题，可以衍生出千姿百态的变种问题，这种题目就非常适合拿来构造解题模型。
0-1背包问题说的是这么回事儿：

有 n 件物品，物品体积用一个名为 w 的数组存起来，物品的价值用一个名为 value 的数组存起来；每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？

注意：每种物品都只有1件

思路分析

这道题如果全靠本能来做，相信不少同学会联想到“暴力枚举法”：暴力枚举每一件物品放或者不放进背包的情况。考虑到每一种物品都面临“放”和“不放”两种选择，因此 n 个物品就对应 2^n 种情况，进而会带来高达 O(2^n)的时间复杂度。这个时间复杂度是众多复杂度中相对来说比较恐怖的“指数量级”，我们是万万不能让这种东西出现在面试题解中的，因此果断放弃它。

遇到最值问题，一定要在可能的解题方案中给动态优化留下一席之地。事实上，背包系列问题，正是动态规划的标准对口问题。

“倒推”法明确状态间关系

现在，假设背包已满，容量已经达到了 c。站在c这个容量终点往后退，考虑从中取出一样物品，那么可能被取出的物品就有 i 种可能性。我们现在尝试表达“取出一件”这个动作对应的变化，我用 f(i, c) 来表示前 i 件物品恰好装入容量为 c 的背包中所能获得的最大价值。现在假设我试图取出的物品是 i，那么只有两种可能：

  1. 第 i 件物品在背包里
  2. 第 i 件物品不在背包里
    1. for(let i=1;i<=n;i++) {
    2.  for(let v=w[i]; v<=c;v++) {
    3.    dp[i][v] = Math.max(dp[i-1][v], dp[i-1][v-w[i]]+value[i])
    4.  }
    5. }

背包问题完整求解代码

  1. // 入参是物品的个数和背包的容量上限，以及物品的重量和价值数组
  2. function knapsack(n, c, w, value) {
  3.     // dp是动态规划的状态保存数组
  4.     const dp = (new Array(c+1)).fill(0)  
  5.     // res 用来记录所有组合方案中的最大值
  6.     let res = -Infinity
  7.     for(let i=1;i<=n;i++) {
  8.         for(let v=c;v>=w[i];v--) {
  9.             // 写出状态转移方程
  10.             dp[v] = Math.max(dp[v], dp[v-w[i]] + value[i])
  11.             // 即时更新最大值
  12.             if(dp[v] > res) {
  13.                 res = dp[v]
  14.             }
  15.         }
  16.     }
  17.     return res
  18. }