编辑代码

#include <stdio.h>

// 定义最大物品数量和最大背包容量
#define MAX_N 100
#define MAX_W 100

// 物品的重量和价值
int weight[MAX_N], value[MAX_N];
// dp数组,dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值
int dp[MAX_N + 1][MAX_W + 1];

// 求解背包问题的函数
int knapsack(int n, int w) {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= w; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (weight[i - 1] <= j) {
                dp[i][j] = dp[i - 1][j] > (dp[i - 1][j - weight[i - 1]] + value[i - 1]) ? dp[i - 1][j] : (dp[i - 1][j - weight[i - 1]] + value[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][w];
}

// 主函数
int main() {
    int n; // 物品数量
    int w; // 背包容量
    printf("请输入物品数量和背包容量:");
    scanf("%d %d", &n, &w);
    printf("请分别输入每个物品的重量和价值:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &weight[i], &value[i]);
    }
    printf("背包所能装下的最大价值为:%d\n", knapsack(n, w));
    return 0;
}