当前位置：首页 > news >正文

0/1 背包问题详解

news 2025/11/18 8:22:46

0/1 背包问题详解

问题简介

0/1 背包问题（Knapsack Problem）是经典的动态规划问题之一。在这个问题中，你有一个容量固定的背包，和若干个物品。每个物品有一个重量和一个价值。目标是在不超过背包容量的前提下，选择一些物品使得它们的总价值最大化。

0/1 背包问题的"0/1"表示每个物品要么放入背包（1），要么不放入背包（0），不能部分放入，也不能重复选择。

问题定义

给定 n 个物品，每个物品有一个重量 w[i] 和价值 v[i]。背包的容量为 W，我们希望选择一些物品使得它们的总重量不超过 W，且总价值最大。

问题公式化

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

目标是最大化物品的总价值，使得：

[
\text{max} \sum_{i=1}^{n} v[i] \cdot x[i]
]
其中，x[i] 表示是否选择第 i 个物品，x[i] = 0 表示不选择，x[i] = 1 表示选择。约束条件是：

[
\sum_{i=1}^{n} w[i] \cdot x[i] \leq W
]

0/1 背包的动态规划解法

思路

动态规划的核心思想是通过构建一个二维数组 dp，来记录每个子问题的最优解。我们定义 dp[i][j] 表示前 i 个物品在背包容量为 j 的情况下可以获得的最大价值。

状态转移方程

对于第 i 个物品，我们有两种选择：

不选择第 i 个物品：那么问题就转化为只考虑前 i-1 个物品，背包容量仍然为 j，此时的最大价值为 dp[i-1][j]。
选择第 i 个物品：前提是 j ≥ w[i]，如果选择第 i 个物品，那么我们需要腾出 w[i] 的空间，剩下的容量是 j - w[i]，因此问题转化为考虑前 i-1 个物品、容量为 j-w[i] 时的最大价值加上当前物品的价值 v[i]，即 dp[i-1][j - w[i]] + v[i]。

因此，状态转移方程为：

[
dp[i][j] = \max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]) \quad \text{当} , j \geq w[i]
]
[
dp[i][j] = dp[i-1][j] \quad \text{当} , j < w[i]
]

边界条件

当 i = 0 或 j = 0 时，dp[i][j] = 0，因为没有物品或者背包容量为 0 时，总价值都为 0。

伪代码实现

伪代码如下：

int knapsack(int W, vector<int> w, vector<int> v, int n) {vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= W; ++j) {if (j >= w[i-1]) {dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1]);} else {dp[i][j] = dp[i-1][j];}}}return dp[n][W];
}

时间与空间复杂度

时间复杂度：动态规划算法的时间复杂度为 O(n * W)，其中 n 是物品的数量，W 是背包的容量。因为我们需要计算 dp 表中的每一个值。
空间复杂度：空间复杂度也是 O(n * W)，因为我们使用了一个二维数组来保存子问题的解。不过，我们可以通过空间优化，将空间复杂度优化为 O(W)，只使用一维数组来存储结果。

空间优化

可以注意到，dp[i][j] 只依赖于 dp[i-1][j] 和 dp[i-1][j - w[i]]，因此我们可以将二维数组简化为一维数组，从后向前更新 dp[j]。

优化后的伪代码如下：

int knapsack(int W, vector<int> w, vector<int> v, int n) {vector<int> dp(W + 1, 0);for (int i = 1; i <= n; ++i) {for (int j = W; j >= w[i-1]; --j) {dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1]);}}return dp[W];
}