0-1 knapsack

Problem Statement

Given the weights and profits of ‘N’ items, we are asked to put these items in a knapsack that has a capacity ‘C’. The goal is to get the maximum profit from the items in the knapsack. Each item can only be selected once, as we don’t have multiple quantities of any item.

Items: { Apple, Orange, Banana, Melon }
Weights: { 2, 3, 1, 4 }
Profits: { 4, 5, 3, 7 }
Knapsack capacity: 5
Output: 10
复制代码

暴力解法

每个 Item 都可以放或者不放，可以对每个元素一次进行递归

export function bruteforce(
  profits: number[],
  weights: number[],
  capacity: number
) {
  const recursive = (i: number, c: number, p: number): number => {
    if (i >= profits.length) return p;

    return Math.max(
      c + weights[i] > capacity
        ? p
        : recursive(i + 1, c + weights[i], p + profits[i]),
      recursive(i + 1, c, p)
    );
  };

  const ans = recursive(0, 0, 0);
  return ans;
}
复制代码

时间复杂度：O(2n)

空间复杂度：O(n)

Top-Down DP

稍微变一个 recursive 的逻辑，recursive 函数表示，把 0~i 范围内的 Item 装入 capacity 为 c 的背包中，能够获得的最大的 profit

可以看到有重复的分支，我们需要做的就是在这个基础上记忆

export function topDown(
  profits: number[],
  weights: number[],
  capacity: number
) {
  const dp: Record<string, number> = {};

  const recursive = (i: number, c: number, p: number): number => {
    if (i >= profits.length) return p;

    const key = `${i}_${c}`;

    if (dp[key]) {
      return dp[key];
    }

    const ans = Math.max(
      c - weights[i] >= 0
        ? recursive(i + 1, c - weights[i], p + profits[i])
        : p,
      recursive(i + 1, c, p)
    );

    return (dp[key] = ans);
  };

  const ans = recursive(0, capacity, 0);
  return ans;
}
复制代码

时间复杂度：O(n * c)，因为记忆化后，最多有 n * c 个子问题

空间复杂度：O(n * c + n)

Bottom-Up DP

dp 记录对于前 i 个元素，当 capacity 为 c 时，能获得的最大 profit，那么

dp[i][c] = max (
	// 不取当前元素
	dp[i-1][c], 
	// 取当前元素
	profits[i] + dp[i-1][c-weights[i]]
)
复制代码

图解如下：

export function bottomUp(
  profits: number[],
  weights: number[],
  capacity: number
) {
  const N = profits.length;
  const dp: number[][] = new Array(N)
    .fill(0)
    .map(() => new Array(capacity + 1).fill(0));

  // 初始化
  for (let i = 0; i < N; i++) dp[i][0] = 0;
  for (let c = 0; c <= capacity; c++) {
    if (weights[0] <= c) dp[0][c] = profits[0];
  }

  // dp
  for (let i = 1; i < N; i++) {
    for (let c = 1; c <= capacity; c++) {
      dp[i][c] = Math.max(
        dp[i - 1][c],
        c < weights[i] ? 0 : profits[i] + dp[i - 1][c - weights[i]]
      );
    }
  }

  return dp[N - 1][capacity];
}
复制代码

时间复杂度：O(n * c)

空间复杂度：O(n * c)

Bottom-Up DP 优化

在计算第 i 个元素的过程中，只需要用到前一次的 dp[c] and dp[c-weight[i]] ，所以，在空间复杂度上我们可以做优化，可以使用同一个数组进行前后两次的记忆

如果 capacity 从 c ~ 0 ，而不是 0 ~ c 循环，去修改 dp[i][c ~ capacity]，可以确保 dp[i][0 ~ c-1] 的值是前一次的，但是，如果按照之前的反过来，计算 dp[i][c] 的时候，dp[i][0 ~ c-1] 已经变成第 i 次的值在存储，所以行不通

export function bottomUp2(
  profits: number[],
  weights: number[],
  capacity: number
) {
  const N = profits.length;
  const dp: number[] = new Array(capacity + 1).fill(0);

  // 初始化
  for (let c = 0; c <= capacity; c++) {
    if (weights[0] <= c) dp[c] = profits[0];
  }

  // dp
  for (let i = 1; i < N; i++) {
    for (let c = capacity; c >= 0; c--) {
      dp[c] = Math.max(
        dp[c],
        c < weights[i] ? 0 : profits[i] + dp[c - weights[i]]
      );
    }
  }

  return dp[capacity];
}
复制代码