编辑代码

#include <stdio.h>

#define NUM_FRUITS 4
#define MAX_WEIGHT 20

typedef struct {
    char name[20];
    int weight;
    int value;
} Fruit;

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

int main() {
    // 初始化水果信息
    Fruit fruits[NUM_FRUITS] = {
        {"苹果", 15, 300},
        {"香蕉", 18, 180},
        {"橘子", 10, 150},
        {"猕猴桃", 9, 270}
    };

    // 初始化动态规划表
    int dp[NUM_FRUITS + 1][MAX_WEIGHT + 1] = {0};

    // 背包问题求解
    knapsack(fruits, dp, NUM_FRUITS, MAX_WEIGHT);

    // 打印装水果的策略
    printStrategy(fruits, dp, NUM_FRUITS, MAX_WEIGHT);

    return 0;
}

void knapsack(Fruit fruits[], int dp[][MAX_WEIGHT + 1], int n, int capacity) {
    for (int i = 1; i <= n; ++i) {
        for (int w = 1; w <= capacity; ++w) {
            if (fruits[i - 1].weight > w) {
                dp[i][w] = dp[i - 1][w];
            } else {
                dp[i][w] = (dp[i - 1][w] > (dp[i - 1][w - fruits[i - 1].weight] + fruits[i - 1].value)) ?
                           dp[i - 1][w] : (dp[i - 1][w - fruits[i - 1].weight] + fruits[i - 1].value);
            }
        }
    }
}

void printStrategy(Fruit fruits[], int dp[][MAX_WEIGHT + 1], int n, int capacity) {
    int w = capacity;
    for (int i = n; i > 0 && w > 0; --i) {
        if (dp[i][w] != dp[i - 1][w]) {
            printf("装入 %s，重量：%dkg，价值：%d元\n", fruits[i - 1].name, fruits[i - 1].weight, fruits[i - 1].value);
            w -= fruits[i - 1].weight;
        }
    }
}