0-1 背包问题

问题

有 N 件物品和一个容量是 V 的背包，每件物品只有一件。第 i 件物品的体积是 v[i]，价值是 w[i]。求解将哪些物品装入背包，可使总体积不超过背包容量，且总价值最大。

示例 1：

输入: N = 3, V = 4, v = [4,2,3], w = [4,2,3]
输出: 4
解释: 只选第一件物品，可使价值最大。

示例 2：

输入: N = 3, V = 5, v = [4,2,3], w = [4,2,3]
输出: 5
解释: 不选第一件物品，选择第二件和第三件物品，可使价值最大。

解答

动态规划（二维数组）

function knapsack(N, V, v, w) {
  // dp[i][j] 表示前 i 件物品，背包容量为 j 时的最大价值
  const dp = Array.from({ length: N + 1 }, () => Array(V + 1).fill(0));
  
  for (let i = 1; i <= N; i++) {
    for (let j = 0; j <= V; j++) {
      // 不选第 i 件物品
      dp[i][j] = dp[i - 1][j];
      
      // 如果能选第 i 件物品，取最大值
      if (j >= v[i - 1]) {
        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1]);
      }
    }
  }
  
  return dp[N][V];
}

动态规划（一维数组优化）

function knapsack(N, V, v, w) {
  const dp = Array(V + 1).fill(0);
  
  for (let i = 0; i < N; i++) {
    // 从后向前遍历，避免重复使用同一物品
    for (let j = V; j >= v[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
    }
  }
  
  return dp[V];
}

关键点

• 状态定义：dp[i][j] 表示前 i 件物品在容量 j 下的最大价值
• 状态转移：对每件物品选择”选”或”不选”，取最大值
• 空间优化：使用一维数组时必须从后向前遍历，防止物品被重复选择
• 时间复杂度 O(N×V)，空间复杂度可优化至 O(V)