0-1背包问题 分数 10 作者 usx程序设计类课程组 单位 绍兴文理学院 给定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[i][j]表示前i个物品，容量为j时的最大价值。

状态转移方程：

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

其中，w[i]和v[i]分别表示第i个物品的重量和价值。

其含义是，要么不选第i个物品，那么最大价值就是前i-1个物品，容量为j时的最大价值，即dp[i-1][j]；要么选第i个物品，那么最大价值就是前i-1个物品，容量为j-w[i]时的最大价值加上第i个物品的价值v[i]，即dp[i-1][j-w[i]]+v[i]。

最终的答案就是dp[n][c]。

接下来是具体的代码实现：

const int MAXN = 401;
const int MAXC = 1501;

int w[MAXN], v[MAXN];
int dp[MAXN][MAXC];

int solve(int n, int c) {
    memset(dp, 0, sizeof(dp)); // 初始化为0
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= c; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]+v[i]);
            }
        }
    }
    return dp[n][c]; // 返回答案
}

完整代码如下：