1.	#include <stdio.h>
2.	
3.	#define MAX_FRUITS 4
4.	#define MAX_WEIGHT 20
5.	
6.	// 结构体表示每种水果的重量和价值
7.	struct Fruit {
8.	    char name[20];
9.	    int weight;
10.	    int value;
11.	};
12.	
13.	// 返回两个整数中的最大值
14.	int max(int a, int b) {
15.	    return (a > b) ? a : b;
16.	}
17.	
18.	// 打印装水果的策略
19.	void printStrategy(int dp[MAX_FRUITS + 1][MAX_WEIGHT + 1], struct Fruit fruits[MAX_FRUITS]) {
20.	    int i = MAX_FRUITS;
21.	    int j = MAX_WEIGHT;
22.	    printf("具体的水果策略为:\n");
23.	
24.	    while (i > 0 && j > 0) {
25.	        if (dp[i][j] != dp[i - 1][j]) {
26.	            printf("%s：%d kg\n", fruits[i - 1].name, fruits[i - 1].weight);
27.	            j -= fruits[i - 1].weight;
28.	            i--; // Move to the next item
29.	        } else {
30.	            i--;
31.	        }
32.	    }
33.	}
34.	
35.	// 动态规划解决背包问题
36.	void knapsack(struct Fruit fruits[MAX_FRUITS]) {
37.	    int dp[MAX_FRUITS + 1][MAX_WEIGHT + 1];
38.	
39.	    for (int i = 0; i <= MAX_FRUITS; i++) {
40.	        for (int j = 0; j <= MAX_WEIGHT; j++) {
41.	            if (i == 0 || j == 0) {
42.	                dp[i][j] = 0;
43.	            } else if (fruits[i - 1].weight <= j) {
44.	                dp[i][j] = max(fruits[i - 1].value + dp[i - 1][j - fruits[i - 1].weight], dp[i - 1][j]);
45.	            } else {
46.	                dp[i][j] = dp[i - 1][j];
47.	            }
48.	        }
49.	    }
50.	
51.	    printf("装入水果的总价值为: %d元\n", dp[MAX_FRUITS][MAX_WEIGHT]);
52.	    printStrategy(dp, fruits);
53.	}
54.	
55.	int main() {
56.	    struct Fruit fruits[MAX_FRUITS] = {
57.	        {"苹果", 15, 300},
58.	        {"香蕉", 18, 180},
59.	        {"橘子", 10, 150},
60.	        {"猕猴桃", 9, 270}
61.	    };
62.	
63.	    knapsack(fruits);
64.	
65.	    return 0;
66.	}