算法设计-0-1背包动态规划（C++）

一、问题阐述

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 表。

四、详细阐述

代码结构

1. 输入部分：从用户那里获取物品数量 n、背包容量 W，以及每个物品的重量和价值。

2. 动态规划求解：使用二维 DP 表来存储子问题的解，逐步填充表格，最终得到最大价值。

3. 输出部分：输出背包能容纳的最大价值。

动态规划表 dp

• dp[i][w] 表示前 i 个物品在背包容量为 w 时的最大价值。

• dp 表的大小为 (n + 1) x (W + 1)，初始化为 0。

状态转移方程

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

  1. 不选择第 i 个物品：最大价值为 dp[i - 1][w]。

  2. 选择第 i 个物品：最大价值为 dp[i - 1][w - weights[i - 1]] + values[i - 1]。

• 最终选择两者中的最大值