递归解法

  • 要么选要么不选要么没法选

    1. def backtrack(w: [], v: [], W, i) -> int:
    2.   # base case
    4.   if i == len(w):
    5.       return 0
    7.   else:
    8.       if w[i] <= W:
    9.           # 在root处理问题
    10.           return max(
    11.               v[i] + backtrack(w, v, W - w[i], i + 1),
    12.               backtrack(w, v, W, i + 1))
    13.       else:
    14.           return backtrack(w, v, W, i + 1)
    15. if __name__ == '__main__':
    16.   W = 4
    17.   w = [2, 1, 3]
    18.   v = [4, 2, 3]
    19.   print(backtrack(w, v, W, 0))

动态规划解法

  • dp[i][j] 前 i 种物品，在背包容量为j 时的最大价值
  • 状态转移方程动态规划-01背包问题 - 图1
  1. def the_01_package(w: [], v: [], W: int) -> int:
  2.     dp = [[0 for j in range(W + 1)] for i in range(len(w) + 1)]
  3.     print(len(dp), len(dp[0]))
  4.     for i in range(1, len(w) + 1):  # 物品
  5.         for j in range(1, W + 1):  # 可用重量
  6.             if w[i - 1] <= j:
  7.                 dp[i][j] = max(
  8.                     v[i - 1] + dp[i - 1][j - w[i - 1]], dp[i - 1][j], dp[i - 1][j])
  10.             else:
  11.                 dp[i][j] = dp[i - 1][j]
  12.     for row in dp:
  13.         print(row)
  16. if __name__ == '__main__':
  17.     W = 4
  18.     w = [2, 1, 3]
  19.     v = [4, 2, 3]
  20.     print(the_01_package(w, v, W))
  1. export {};
  2. namespace pkg01_dfs {
  3.     function maxValue(W: number, wt: number[], val: number[]) {
  4.         function dfs(i: number, W: number): number {
  5.             /* base case */
  6.             if (i === wt.length || W <= 0) {
  7.                 return 0;
  8.             }
  9.             /* make progress */
  10.             // 可选
  11.             if (W >= wt[i]) {
  12.                 return Math.max(val[i] + dfs(i + 1, W - wt[i]), dfs(i + 1, W));
  13.             }
  14.             // 不能选
  16.             return dfs(i + 1, W);
  17.         }
  18.         return dfs(0, W);
  19.     }
  20.     // console.log(maxValue(4, [2, 1, 3], [4, 2, 3]));
  21. }
  23. namespace pkg01_dp {
  24.     function maxValue(W: number, wt: number[], value: number[]) {
  25.         /*
  26.          * state: dp[w][i] => 背包容量为w的情况下，使用前i件物品能得到的最大价值
  27.          * base case: dp[0][*] = 0 dp[*][0] = 0
  28.          * make change:
  29.          *      dp[w][i] = {
  30.          *               dp[w][i-1] || dp [w-wi][i-1]
  31.          *
  32.          */
  33.         const dp: number[][] = new Array(W + 1)
  34.             .fill(0)
  35.             .map(() => new Array(wt.length + 1).fill(0));
  37.         /* Base case */
  38.         for (let i = 0; i <= wt.length; i++) {
  39.             dp[0][i] = 0;
  40.         }
  42.         for (let i = 0; i <= W; i++) {
  43.             dp[i][0] = 0;
  44.         }
  45.         /* Make progress */
  46.         for (let w = 1; w <= W; w++) {
  47.             for (let i = 1; i <= wt.length; i++) {
  48.                 if (w >= wt[i - 1]) {
  49.                     dp[w][i] = Math.max(
  50.                         value[i - 1] + dp[w - wt[i - 1]][i - 1],
  51.                         dp[w][i - 1]
  52.                     );
  53.                 } else {
  54.                     dp[w][i] = dp[w][i - 1];
  55.                 }
  56.             }
  57.         }
  58.         return dp[W][wt.length];
  59.     }
  60.     console.log(maxValue(4, [2, 1, 3], [4, 2, 3]));
  61. }

总结

  • 二维动态规划
  • 动态规划与回溯
    • 动态规划： 自顶向下考虑， 自底向上求解
    • 回溯： 自顶向下考虑， 自顶向下求解
    • 可以用回溯法思考状态转移方程