C++ 实现 0-1 背包问题：最大价值求解

问题描述:

给定 n 种物品（每种仅一个）和一个容量为 c 的背包，要求选择物品装入背包，使得装入背包中物品的总价值最大。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据输入 3 行，

第 1 行为两个整数 n (1 ≤ n ≤ 400) 和 c (1 ≤ c ≤ 1500)，分别表示物品数量与背包容量，
第二行为 n 个物品的重量 w[i] (1 ≤ i ≤ n)，
第三行为这 n 个物品的价值 v[i] (1 ≤ i ≤ n)。物品重量、价值都为整数。

输出格式:

对于每组测试，在一行上输出一个整数，表示装入背包的最大总价值（结果保证在 2^31 - 1 范围内）。

输入样例:

4 9
2 3 4 5
3 4 5 7
25 100
42 6 48 13 38 124 8 17 41 25 41 26 47 41 171 25 7 30 35 7 17 32 45 27 38
49 19 53 40 22 4 36 20 49 25 61 48 67 34 57 52 46 45 33 41 20 38 34 58 63

输出样例:

12
292

思路:

0-1 背包问题，用 DP 求解。dp[i][j] 表示前 i 个物品重量不超过 j 的最大价值。

状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。

C++ 代码:

#include <iostream>
using namespace std;

int main() {
    int n, c;
    while (cin >> n >> c) {
        int w[401], v[401];
        for (int i = 1; i <= n; i++) {
            cin >> w[i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> v[i];
        }
        int dp[401][1501] = {0};
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= c; j++) {
                if (j >= w[i]) {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        cout << dp[n][c] << endl;
    }
    return 0;
}

解释:

dp[i][j] 数组存储了前 i 个物品重量不超过 j 的最大价值。
初始化 dp[0][j] 为 0，表示没有物品时价值为 0。
在循环中，对于每个物品 i 和背包容量 j，我们根据状态转移方程判断是否选取当前物品。
如果 j 大于等于当前物品的重量 w[i]，则可以选择将当前物品放入背包，此时最大价值为 dp[i-1][j-w[i]] + v[i]，即前 i-1 个物品在剩余容量 j-w[i] 下的最大价值加上当前物品的价值。
如果 j 小于当前物品的重量 w[i]，则不能将当前物品放入背包，此时最大价值等于前 i-1 个物品在容量 j 下的最大价值，即 dp[i-1][j]。
最终 dp[n][c] 即为所有物品在背包容量 c 下的最大价值。