编辑代码

#include <stdio.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int values[] = {3000, 2000, 1500};
    int weights[] = {4, 3, 1};
    char* items[] = {"音响", "笔记本电脑", "吉他"};
    int W = 4;                           // 背包的最大重量
    int n = sizeof(values) / sizeof(values[0]); // 物品的数量
    int dp[n+1][W+1];
    int selected[n];

    // 初始化动态规划表和选择数组
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = 0;
        }
        selected[i] = 0;
    }

    // 填充动态规划表
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (weights[i-1] <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // 回溯找到选择的物品
    int j = W;
    for (int i = n; i > 0; i--) {
        if (dp[i][j] != dp[i-1][j]) {
            selected[i-1] = 1; // 选择了第i个物品
            j -= weights[i-1];
        }
    }

    printf("可盗窃的商品最大价值为：%d\n", dp[n][W]);
    printf("选择的商品为：");
    for (int i = 0; i < n; i++) {
        if (selected[i] == 1) {
            printf("%s ", items[i]);
        }
    }
    
    return 0;
}