0-1 背包问题

问题描述

假设你有一个容量为 W 的背包，以及 n 件物品。每件物品有两个属性：

  • 重量：（第 i 件物品的重量）
  • 价值：（第 i 件物品的价值）

你的目标是选择一些物品放入背包，使得：

  1. 这些物品的总重量不超过背包容量 W。
  2. 这些物品的总价值最大。

注意：每件物品只能选择一次（要么放入背包，要么不放入），因此称为 0-1 背包问题。

动态规划解法

  1. 定义状态

    • 设 表示前 i 件物品在容量为 j 的背包中能获得的最大价值。
      • i：物品编号（从 1 到 n）。
      • j：背包容量（从 0 到 W）。

  2. 状态转移方程

    对于每件物品 i，有两种选择：

    1. 不放入背包：（价值不变）。
    2. 放入背包：（价值增加）。

    因此，状态转移方程为：

  3. 初始化

    • ：没有物品时，价值为 0。
    • ：背包容量为 0 时，价值为 0。

  4. 最终结果

    即为问题的解，表示前 n 件物品在容量为 W 的背包中能获得的最大价值。

代码实现

 1  /* 0-1 背包：动态规划 */
 2  int knapsackDP(int[] wgt, int[] val, int cap) {
 3      int n = wgt.length;
 4      // 初始化 dp 表
 5      int[][] dp = new int[n + 1][cap + 1];
 6      // 状态转移
 7      for (int i = 1; i <= n; i++) {
 8          for (int c = 1; c <= cap; c++) {
 9              if (wgt[i - 1] > c) {
10                  // 若超过背包容量，则不选物品 i
11                  dp[i][c] = dp[i - 1][c];
12              } else {
13                  // 不选和选物品 i 这两种方案的较大值
14                  dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
15              }
16          }
17      }
18      return dp[n][cap];
19  }
购物车