编辑代码

#include <stdio.h>
#include <stdbool.h>

// 定义最大水果数量和最大背包承重
#define MAX_FRUITS 4
#define MAX_CAPACITY 20

// 物品结构体
struct Fruit {
    char name[10];
    int weight;
    int value;
};

// 函数声明
void printStrategy(struct Fruit fruits[], int dp[MAX_FRUITS + 1][MAX_CAPACITY + 1], int n, int capacity);

int main() {
    // 水果信息
    struct Fruit fruits[MAX_FRUITS] = {{"苹果", 15, 300},
                                       {"香蕉", 18, 180},
                                       {"橘子", 10, 150},
                                       {"猕猴桃", 9, 270}};
    int n = sizeof(fruits) / sizeof(fruits[0]);
    // 初始化二维数组 dp
    int dp[MAX_FRUITS + 1][MAX_CAPACITY + 1];
    // 动态规划过程
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= MAX_CAPACITY; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (fruits[i - 1].weight <= j) {
                dp[i][j] = (dp[i - 1][j] > dp[i - 1][j - fruits[i - 1].weight] + fruits[i - 1].value) ?
                           dp[i - 1][j] : dp[i - 1][j - fruits[i - 1].weight] + fruits[i - 1].value;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    // 输出所选水果的策略
    printStrategy(fruits, dp, n, MAX_CAPACITY);
    return 0;
}

// 输出所选水果的策略
void printStrategy(struct Fruit fruits[], int dp[MAX_FRUITS + 1][MAX_CAPACITY + 1], int n, int capacity) {
    printf("装入背包：\n");
    int i = n;
    int j = capacity;
    while (i > 0 && j > 0) {
        if (dp[i][j] != dp[i - 1][j]) {
            // 选择了当前水果
            printf("%s（重量：%dkg，价值：%d元）\n", fruits[i - 1].name, fruits[i - 1].weight, fruits[i - 1].value);
            j -= fruits[i - 1].weight;
        }
        i--;
    }
}