问题描述

给定 n 件物品和容量为 V 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包，可使这些物品的总重量不超过背包容量，且总价值最大。

问题分析

对于这类优化问题，我们首先考虑穷举法。使用深度优先搜索或广度优先搜索确实能得到解，但时间复杂度达到指数级 O(2^n)，对于 n=1000 的数据规模完全不可行。贪心算法虽然效率高，但往往只能得到近似解，无法保证最优性。因此，动态规划成为解决此类问题的理想选择。

动态规划适用场景

• 问题可以通过递归或搜索思路描述，但直接求解效率低下
• 求解有限集合的极值问题（最大值、最小值等）
• 问题状态可以用数字组合表示，如本例中的 f(i, j)

动态规划解题步骤

第一步：状态定义

定义 dp[i][j] 表示从前 i 件物品中选择，在背包容量不超过 j 的情况下能获得的最大价值。这个状态包含两个维度：物品数量和剩余容量。

第二步：状态转移方程

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

• 不选第 i 件物品：dp[i][j] = dp[i-1][j]
• 选第 i 件物品（前提是容量足够）：dp[i][j] = dp[i-1][j-w[i]] + v[i]

综合两种选择，状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) （当 j ≥ w[i] 时）

基础实现代码

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

const int MAXN = 1005;

int dp[MAXN][MAXN];
int weight[MAXN], value[MAXN];

int main() {
    int n, capacity;
    cin >> n >> capacity;
    
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= weight[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-weight[i]] + value[i]);
            }
        }
    }
    
    cout << dp[n][capacity] << endl;
    return 0;
}

空间优化

观察状态转移方程可以发现，计算第 i 行时只依赖第 i-1 行的数据。因此可以使用滚动数组技术，将二维数组压缩为一维数组，将空间复杂度从 O(nV) 降到 O(V)。

需要注意的是，为了避免重复使用同一件物品，内层循环需要从后向前遍历容量。

优化后实现代码

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

const int MAXN = 1005;

int dp[MAXN];
int weight[MAXN], value[MAXN];

int main() {
    int n, capacity;
    cin >> n >> capacity;
    
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = capacity; j >= weight[i]; j--) {
            dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
        }
    }
    
    cout << dp[capacity] << endl;
    return 0;
}

通过空间优化，我们将二维动态规划转化为高效的一维实现，既保持了正确性，又显著降低了内存占用。这种优化技巧在背包问题中非常常用，值得深入理解。