背包问题

背包问题是动态规划中的经典问题，它有多种变体，是算法竞赛中的常见题型。本章将详细介绍各类背包问题的解题思路和技巧。

01背包问题

【问题定义】有N件物品和一个容量为V的背包，每件物品有且只有一件。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包，可使这些物品的总重量不超过背包容量，且总价值最大。

基本思路

使用动态规划求解，设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])  (if j ≥ w[i])
dp[i][j] = dp[i-1][j]  (if j < w[i])

代码实现

二维数组实现：

// 01背包问题的二维数组实现
int knapsack01(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    // dp[i][j]: 考虑前i个物品，背包容量j下的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (j < weights[i-1]) {
                // 背包容量不足，无法放入第i个物品
                dp[i][j] = dp[i-1][j];
            } else {
                // 可以选择放或不放第i个物品
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
            }
        }
    }

    return dp[n][capacity];
}

空间优化

由于dp[i][j]只与dp[i-1][j]和dp[i-1][j-w[i]]有关，可以使用一维数组优化空间：

// 01背包问题的一维数组优化
int knapsack01_optimized(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            // 注意这里的遍历顺序：从大到小逆序遍历
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);
        }
    }

    return dp[capacity];
}

【注意】一维数组实现中，必须从大到小逆序遍历容量j，确保每个物品只被考虑一次。

完全背包问题

【问题定义】有N种物品和一个容量为V的背包，每种物品有无限件。第i种物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包，可使这些物品的总重量不超过背包容量，且总价值最大。

状态转移方程

与01背包不同，完全背包问题中每种物品可以选择多次，因此状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])  (if j ≥ w[i])
dp[i][j] = dp[i-1][j]  (if j < w[i])

注意区别：01背包中是dp[i-1][j-w[i]] + v[i]，而完全背包中是dp[i][j-w[i]] + v[i]，因为物品i可以被重复选择。

代码实现

// 完全背包问题
int unboundedKnapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (j < weights[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i-1]] + values[i-1]);
            }
        }
    }

    return dp[n][capacity];
}

空间优化

完全背包的一维数组优化与01背包类似，但遍历顺序不同：

// 完全背包问题的一维数组优化
int unboundedKnapsack_optimized(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = weights[i]; j <= capacity; j++) {
            // 注意这里的遍历顺序：从小到大正序遍历
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);
        }
    }

    return dp[capacity];
}

【注意】与01背包不同，完全背包需要从小到大正序遍历容量j，确保每个物品可以被多次选择。

多重背包问题

【问题定义】有N种物品和一个容量为V的背包。第i种物品最多有k[i]件，每件重量为w[i]，价值为v[i]。求解将哪些物品装入背包，可使这些物品的总重量不超过背包容量，且总价值最大。

基本思路

多重背包可以看作是01背包和完全背包的混合：每种物品有限定数量。

朴素解法

通过枚举每种物品选择的数量来解决：

// 多重背包问题的朴素解法
int multiplePack(vector<int>& weights, vector<int>& values, vector<int>& counts, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= 0; j--) {
            for (int k = 1; k <= counts[i] && k * weights[i] <= j; k++) {
                dp[j] = max(dp[j], dp[j - k * weights[i]] + k * values[i]);
            }
        }
    }

    return dp[capacity];
}

二进制优化

当物品数量较大时，可以使用二进制优化来降低时间复杂度：

// 多重背包问题的二进制优化
int multiplePack_binary(vector<int>& weights, vector<int>& values, vector<int>& counts, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);

    // 将多个相同物品拆分成二进制组
    vector<int> new_weights, new_values;

    for (int i = 0; i < n; i++) {
        int count = counts[i];
        for (int k = 1; k <= count; k *= 2) {
            new_weights.push_back(weights[i] * k);
            new_values.push_back(values[i] * k);
            count -= k;
        }
        if (count > 0) {
            new_weights.push_back(weights[i] * count);
            new_values.push_back(values[i] * count);
        }
    }

    // 转化为01背包问题
    for (int i = 0; i < new_weights.size(); i++) {
        for (int j = capacity; j >= new_weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - new_weights[i]] + new_values[i]);
        }
    }

    return dp[capacity];
}

混合背包问题

【问题定义】有N种物品和一个容量为V的背包。物品有三类：

• 第一类物品只能用1次（01背包）
• 第二类物品可以用无限次（完全背包）
• 第三类物品最多用k次（多重背包）

解题思路

根据物品的类型分别处理：

// 混合背包问题
int mixedKnapsack(vector<int>& weights, vector<int>& values, vector<int>& types, vector<int>& counts, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; i++) {
        if (types[i] == 0) {  // 01背包
            for (int j = capacity; j >= weights[i]; j--) {
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
            }
        } else if (types[i] == 1) {  // 完全背包
            for (int j = weights[i]; j <= capacity; j++) {
                dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
            }
        } else {  // 多重背包
            // 二进制优化
            int count = counts[i];
            for (int k = 1; k <= count; k *= 2) {
                int new_weight = weights[i] * k;
                int new_value = values[i] * k;
                for (int j = capacity; j >= new_weight; j--) {
                    dp[j] = max(dp[j], dp[j - new_weight] + new_value);
                }
                count -= k;
            }
            if (count > 0) {
                int new_weight = weights[i] * count;
                int new_value = values[i] * count;
                for (int j = capacity; j >= new_weight; j--) {
                    dp[j] = max(dp[j], dp[j - new_weight] + new_value);
                }
            }
        }
    }

    return dp[capacity];
}

分组背包问题

【问题定义】有N组物品和一个容量为V的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的重量是w[i][j]，价值是v[i][j]，其中i是组号，j是组内编号。求解将哪些物品装入背包，可使物品总重量不超过背包容量，且总价值最大。

解题思路

针对每一组物品，枚举该组选择哪件物品：

// 分组背包问题
int groupKnapsack(vector<vector<int>>& weights, vector<vector<int>>& values, int capacity) {
    int n = weights.size();  // 组数
    vector<int> dp(capacity + 1, 0);

    for (int i = 0; i < n; i++) {  // 枚举每一组
        for (int j = capacity; j >= 0; j--) {  // 枚举背包容量
            for (int k = 0; k < weights[i].size(); k++) {  // 枚举该组的每个物品
                if (j >= weights[i][k]) {
                    dp[j] = max(dp[j], dp[j - weights[i][k]] + values[i][k]);
                }
            }
        }
    }

    return dp[capacity];
}

二维背包问题

【问题定义】有N件物品和一个容量为(V,M)的背包，这里有两个限制维度（如体积和重量）。第i件物品需要消耗背包的空间为(v[i],m[i])，价值是w[i]。求解将哪些物品装入背包，可使物品的总体积不超过V，总重量不超过M，且总价值最大。

解题思路

扩展到三维DP数组，dp[i][j][k]表示考虑前i个物品，体积不超过j，重量不超过k的最大价值：

// 二维费用背包问题
int twoDimensionKnapsack(vector<int>& weights, vector<int>& volumes, vector<int>& values, int capacity_weight, int capacity_volume) {
    int n = weights.size();
    vector<vector<int>> dp(capacity_weight + 1, vector<int>(capacity_volume + 1, 0));

    for (int i = 0; i < n; i++) {
        for (int j = capacity_weight; j >= weights[i]; j--) {
            for (int k = capacity_volume; k >= volumes[i]; k--) {
                dp[j][k] = max(dp[j][k], dp[j - weights[i]][k - volumes[i]] + values[i]);
            }
        }
    }

    return dp[capacity_weight][capacity_volume];
}

背包问题求方案数

【问题变形】除了求最大价值外，还可能需要求达到最大价值的方案数量。

解题思路

维护两个DP数组，一个记录最大价值，一个记录达到该价值的方案数：

// 背包问题求方案数
pair<int, int> knapsackWithCount(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    int mod = 1e9 + 7;
    vector<int> dp(capacity + 1, 0);  // 最大价值
    vector<int> count(capacity + 1, 0);  // 方案数量
    count[0] = 1;  // 初始状态有1种方案

    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            int new_value = dp[j - weights[i]] + values[i];
            if (new_value > dp[j]) {
                // 找到更大的价值，更新最大价值和方案数
                dp[j] = new_value;
                count[j] = count[j - weights[i]];
            } else if (new_value == dp[j]) {
                // 相同价值，方案数累加
                count[j] = (count[j] + count[j - weights[i]]) % mod;
            }
        }
    }

    return {dp[capacity], count[capacity]};
}

背包问题输出方案

【问题变形】需要输出具体选择了哪些物品。

解题思路

记录每一步的选择，然后回溯：

// 背包问题输出方案
vector<int> knapsackWithSolution(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    vector<vector<bool>> selected(n + 1, vector<bool>(capacity + 1, false));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (j < weights[i-1]) {
                dp[i][j] = dp[i-1][j];
                selected[i][j] = false;
            } else {
                int not_take = dp[i-1][j];
                int take = dp[i-1][j-weights[i-1]] + values[i-1];
                if (take > not_take) {
                    dp[i][j] = take;
                    selected[i][j] = true;
                } else {
                    dp[i][j] = not_take;
                    selected[i][j] = false;
                }
            }
        }
    }

    // 回溯找出选择的物品
    vector<int> solution;
    int i = n, j = capacity;
    while (i > 0) {
        if (selected[i][j]) {
            solution.push_back(i-1);  // 选择了第i个物品
            j -= weights[i-1];
        }
        i--;
    }

    return solution;
}

多维背包、泛化背包问题

背包问题可以扩展到多个维度，或者添加更多的约束条件。解决这类问题的核心思想是理解状态定义和转移方程，然后根据具体问题调整DP数组的维度和转移方式。

背包问题变种

恰好装满背包

当要求恰好装满背包时，初始化方式有所不同：

• dp[0] = 0
• dp[j] = -∞ (j > 0)

// 恰好装满背包的01背包问题
int knapsack01_exact(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, INT_MIN); // 除了dp[0]=0外，其他初始化为负无穷
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);
        }
    }

    // 如果结果为负无穷，表示无法恰好装满
    return dp[capacity] < 0 ? -1 : dp[capacity];
}

最小代价问题

有时背包问题可以反向思考，寻找达到某一目标的最小代价：

// 最小代价背包问题
int minCostKnapsack(vector<int>& weights, vector<int>& costs, int target_weight) {
    int n = weights.size();
    vector<int> dp(target_weight + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = target_weight; j >= weights[i]; j--) {
            if (dp[j - weights[i]] != INT_MAX) {
                dp[j] = min(dp[j], dp[j - weights[i]] + costs[i]);
            }
        }
    }

    return dp[target_weight] == INT_MAX ? -1 : dp[target_weight];
}

背包问题解题技巧

1. 正确的遍历顺序：
   • 01背包：容量逆序遍历
   • 完全背包：容量正序遍历
2. 空间优化：多数背包问题都可以使用一维DP数组优化空间
3. 初始化：根据问题要求（是否需要恰好装满）选择合适的初始化方式
4. 转换思路：某些变种问题通过转换思路，可以归约为标准背包问题

练习题目推荐

1. POJ 3624: Charm Bracelet (经典01背包)
2. POJ 1276: Cash Machine (完全背包)
3. POJ 1742: Coins (多重背包)
4. POJ 2392: Space Elevator (分组背包变形)
5. POJ 1837: Balance (带负重的背包)
6. POJ 3260: The Fewest Coins (混合背包)

总结

背包问题是算法竞赛中的经典问题，掌握其基本思路和各种变形对于解决动态规划问题非常有帮助。通过不断练习，你可以熟悉各种背包问题的解题模式，并将这些思想迁移到更复杂的问题中。