编辑代码

#include <stdio.h>

// 返回两个数中的较大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 打印装载策略
void printStrategy(int K[][21], int wt[], int val[], int n) {
    int i = n, w = 20;
    while (i > 0 && w > 0) {
        if (K[i][w] != K[i - 1][w]) {
            printf("%dkg的%s装入背包\n", wt[i - 1], (i == 1) ? "苹果" : (i == 2) ? "香蕉" : (i == 3) ? "橘子" : "猕猴桃");
            w -= wt[i - 1];
        }
        i--;
    }
}

// 动态规划求解背包问题
int pack(int W, int wt[], int val[], int n) {
    int i, w;
    int K[n + 1][W + 1]; // 创建一个二维数组来保存中间结果
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0; // 初始化边界条件
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]); // 根据状态转移方程更新K[i][w]
            else
                K[i][w] = K[i - 1][w]; // 保持不装入当前物品的状态
        }
    }
    printStrategy(K, wt, val, n); // 打印装载策略
    return K[n][W]; // 返回最大总价值
}

int main() {
    int val[] = {300, 180, 150, 270};
    int wt[] = {15, 18, 10, 9};
    int W = 20;
    int n = sizeof(val) / sizeof(val[0]);
    printf("最大总价值: %d\n", pack(W, wt, val, n)); // 调用pack函数求解背包问题
    return 0;
}