背包问题动态规划详解：C++实现0-1背包与完全背包

什么是背包问题？

背包问题（Knapsack Problem） 是计算机科学中经典的动态规划问题。给定一组物品，每个物品有重量和价值，在不超过背包容量的情况下，选择物品使得总价值最大化。

常见的背包问题类型包括：

0-1背包：每种物品只能选0个或1个
完全背包：每种物品可以选无限个
多重背包：每种物品有数量限制
分组背包：物品分组，每组最多选一个

0-1 背包问题描述

有 n 件物品和一个容量为 W 的背包。第 i 件物品的重量为 w[i]，价值为 v[i]。求解将哪些物品装入背包可使价值总和最大。

动态规划解法

定义 dp[i][w] 表示：考虑前 i 件物品，背包容量为 w 时的最大价值。

状态转移方程：

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

即：对于第 i 件物品，可以选择不选或选（前提是容量够）

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

// 0-1 背包二维 DP
int knapsack_2d(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            // 不选第 i 件物品
            dp[i][w] = dp[i-1][w];
            
            // 选第 i 件物品（容量够的情况下）
            if (w >= weight[i-1]) {
                dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);
            }
        }
    }
    
    return dp[n][W];
}

// 0-01 背包一维 DP（空间优化）
int knapsack_1d(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 倒序遍历，确保每件物品只选一次
        for (int w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    
    return dp[W];
}

// 记录选择方案
vector<int> knapsack_with_choice(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    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++) {
            dp[i][w] = dp[i-1][w];
            if (w >= weight[i-1]) {
                dp[i][w] = max(dp[i][w], dp[i-1][w - weight[i-1]] + value[i-1]);
            }
        }
    }
    
    // 回溯找出选择了哪些物品
    vector<int> chosen;
    int w = W;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {
            chosen.push_back(i - 1);  // 选择了第 i-1 件物品
            w -= weight[i-1];
        }
    }
    reverse(chosen.begin(), chosen.end());
    
    return chosen;
}

int main() {
    int n = 4;
    vector<int> weight = {2, 3, 4, 5};
    vector<int> value = {3, 4, 5, 6};
    int W = 8;
    
    cout << "物品信息:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "物品" << i << ": 重量=" << weight[i] << ", 价值=" << value[i] << endl;
    }
    cout << "背包容量: " << W << endl;
    
    cout << "\n最大价值 (二维DP): " << knapsack_2d(weight, value, W) << endl;
    cout << "最大价值 (一维DP): " << knapsack_1d(weight, value, W) << endl;
    
    // 输出选择了哪些物品
    vector<int> chosen = knapsack_with_choice(weight, value, W);
    cout << "选择的物品: ";
    for (int idx : chosen) {
        cout << idx << "(w=" << weight[idx] << ",v=" << value[idx] << ") ";
    }
    cout << endl;
    
    return 0;
}

完全背包（每种物品无限件）

// 完全背包一维 DP
int complete_knapsack(vector<int>& weight, vector<int>& value, int W) {
    int n = weight.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 正序遍历，完全背包可以重复选
        for (int w = weight[i]; w <= W; w++) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }
    
    return dp[W];
}

复杂度分析

方法	时间复杂度	空间复杂度
二维 DP	O(n × W)	O(n × W)
一维 DP	O(n × W)	O(W)

背包问题的变形

多重背包：将物品数量拆分转化为 0-1 背包
分组背包：每组只能选一个
二维背包：两个限制条件（如重量和体积）

总结

背包问题是动态规划的经典入门题目。掌握 0-1 背包的核心思想（选或不选），对于理解其他动态规划问题非常有帮助。空间优化技巧（从二维降到一维）也是常见的优化手段。