一、问题阐述
0-1 背包问题的目标是在给定背包容量 W 的情况下，从 n 个物品中选择一些物品放入背包，使得背包中物品的总价值最大。每个物品只能选择一次（即要么放入背包，要么不放入）。
二、代码
#include <iostream>
#include <vector>
using namespace std;// 动态规划解决 0-1 背包问题
int knapsack(int W, const vector<int>& weights, const vector<int>& values, int n) {// 创建二维 DP 表vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));// 填充 DP 表for (int i = 1; i <= n; ++i) {for (int w = 0; w <= W; ++w) {if (weights[i - 1] <= w) {// 选择第 i 个物品dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);} else {// 不选择第 i 个物品dp[i][w] = dp[i - 1][w];}}}// 返回最大价值return dp[n][W];
}int main() {// 输入int n, W;cout << "请输入物品数量 n 和背包的最大承重 W: ";cin >> n >> W;vector<int> weights(n);vector<int> values(n);cout << "请输入每个物品的重量: ";for (int i = 0; i < n; ++i) {cin >> weights[i];}cout << "请输入每个物品的价值: ";for (int i = 0; i < n; ++i) {cin >> values[i];}// 计算最大价值int max_value = knapsack(W, weights, values, n);// 输出结果cout << "最大总价值为: " << max_value << endl;return 0;
}
三、复杂度
-
时间复杂度：
O(n * W)，其中n是物品数量，W是背包容量。 -
空间复杂度：
O(n * W)，用于存储 DP 表。
四、详细阐述
代码结构
-
输入部分：从用户那里获取物品数量
n、背包容量W，以及每个物品的重量和价值。 -
动态规划求解：使用二维 DP 表来存储子问题的解，逐步填充表格，最终得到最大价值。
-
输出部分：输出背包能容纳的最大价值。
动态规划表 dp
-
dp[i][w]表示前i个物品在背包容量为w时的最大价值。 -
dp表的大小为(n + 1) x (W + 1)，初始化为 0。
状态转移方程
-
对于第
i个物品，有两种选择：-
不选择第
i个物品：最大价值为dp[i - 1][w]。 -
选择第
i个物品：最大价值为dp[i - 1][w - weights[i - 1]] + values[i - 1]。
-
-
最终选择两者中的最大值
