0-1背包问题基础概念

一、问题描述

给定一个容量为 W 的背包和 n 个物品。每个物品有一个重量 w[i] 和价值 v[i]。每个物品只能选或不选（即“0-1”），求在不超过背包容量的前提下，所能获得的最大总价值。

输入：

• 背包容量 W（int）
• 物品数量 n（int）
• 每个物品的重量 w[i]（int[]）
• 每个物品的价值 v[i]（int[]）

输出：

• 最大总价值（int）

---

二、建模分析

定义 dp[i][j] 表示：前 i 个物品中选取若干个，放入容量为 j 的背包中所能获得的最大价值。

状态转移方程：

• 如果不选第 i 个物品：

  dp[i][j] = dp[i - 1][j]
  

• 如果选第 i 个物品（前提是 j >= w[i]）：

  dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])
  

初始条件：dp[0][*] = 0（0 个物品时，无论容量多少，价值都是 0）

最终答案：dp[n][W]

---

三、Java 实现（二维 DP）

public class Knapsack01 {public static int knapsack(int[] weights, int[] values, int W) {int n = weights.length;int[][] dp = new int[n + 1][W + 1];for (int i = 1; i <= n; i++) {int wi = weights[i - 1];int vi = values[i - 1];for (int j = 0; j <= W; j++) {if (j < wi) {dp[i][j] = dp[i - 1][j]; // 装不下} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wi] + vi);}}}return dp[n][W];}public static void main(String[] args) {int[] weights = {2, 1, 3};int[] values = {4, 2, 3};int W = 4;System.out.println(knapsack(weights, values, W)); // 输出最大价值}
}

---

四、空间优化（滚动数组）

二维数组空间复杂度为 O(nW)，可以用一维数组降为 O(W)：

public class Knapsack01Optimized {public static int knapsack(int[] weights, int[] values, int W) {int n = weights.length;int[] dp = new int[W + 1];for (int i = 0; i < n; i++) {for (int j = W; j >= weights[i]; j--) {dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);}}return dp[W];}
}

⚠️ **注意：**必须倒序遍历 j，否则会重复使用同一物品，变成“完全背包”问题。

---

五、实际应用场景

• 项目预算分配（有限资源选择最优组合）
• 云资源调度（选择若干任务部署到有限资源池）
• 投资组合选择（限定资金下选择最大收益）
• 嵌入式设备资源优化（内存/能耗限制下选择模块）

---

六、变种问题（可扩展）

问题类型	描述	变化点
完全背包	每个物品可以选多次	内层循环从小到大
多重背包	每个物品有限个数	转换成多个“0-1背包项”
多维背包	背包有多个限制条件（如体积）	dp[i][j][k]... 多维数组
分组背包	多个物品组，每组最多选一个	分组循环 + DP