// 导入java.util包中的ArrayList和List类，用于动态数组和列表操作
import java.util.ArrayList;
import java.util.List;
// 定义一个公共类KnapsackProblem，它包含一个内部类Fruit和主方法main
public class KnapsackProblem {
// 定义一个内部类Fruit，用于表示背包中的物品
// Fruit类包含三个属性：name（名称）、weight（重量）和value（价值）
static class Fruit {
String name;
int weight;
int value;
// 构造函数，用于初始化Fruit对象的属性
public Fruit(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
}
// 主方法，程序的入口点
public static void main(String[] args) {
// 创建一个Fruit对象数组fruits，包含四种水果及其重量和价值
Fruit[] fruits = {
new Fruit("苹果", 15, 300),
new Fruit("香蕉", 18, 180),
new Fruit("橘子", 10, 150),
new Fruit("猕猴桃", 9, 270)
};
// 定义背包的容量capacity为20
int capacity = 20;
// 定义水果的数量n为fruits数组的长度
int n = fruits.length;
// 定义一个二维数组dp，用于存储中间状态，其大小为(n+1) * (capacity+1)
int[][] dp = new int[n + 1][capacity + 1];
// 使用双重循环填充dp数组
// 外层循环遍历水果的数量i，内层循环遍历背包的容量j
for (int i = 1; i <= n; i++) { // 外层循环，i从1到n
for (int j = 1; j <= capacity; j++) { // 内层循环，j从1到capacity
// 如果当前水果的重量小于等于当前背包容量j，则有两种选择：放入或不放入背包
if (fruits[i - 1].weight <= j) { // 判断是否可以放入当前水果
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - fruits[i - 1].weight] + fruits[i - 1].value); // 选择放入当前水果或不放当前水果中的较大值
} else { // 如果当前水果的重量大于当前背包容量j，则不能放入背包，直接继承前一个状态的值
dp[i][j] = dp[i - 1][j]; // 继承前一个状态的值
}
}
}
// 获取在背包容量为capacity时能够获得的最大价值，并存储在变量maxValue中
int maxValue = dp[n][capacity]; // 获取最大价值
System.out.println("装水果的最大价值为：" + maxValue); // 输出最大价值
// 创建一个ArrayList列表来存储装水果的策略（即放入背包的水果名称）
List<String> strategy = new ArrayList<>(); // 初始化策略列表为空列表
int w = capacity; // w用于表示当前背包剩余容量，初始值为背包容量capacity
for (int i = n; i > 0 && maxValue > 0; i--) { // 从最后一个水果开始向前遍历，直到第一个水果或者最大价值为0为止
if (maxValue != dp[i - 1][w]) { // 如果当前水果放入背包后不能获得最大价值，则将其加入策略列表中，并更新剩余容量和最大价值
strategy.add(fruits[i - 1].name); // 将当前水果名称加入策略列表中
maxValue -= fruits[i - 1].value; // 从最大价值中减去当前水果的价值
w -= fruits[i - 1].weight; // 从剩余容量中减去当前水果的重量
}
}
// 输出装水果的策略（即放入背包的水果名称）列表，从后往前输出，因为最后加入策略列表的是最先 放入背包的水果。
System.out.println("装水果的策略：");
for (int i = strategy.size() - 1; i >= 0; i--) { // 从策略列表的最后一个元素开始向前遍历
System.out.println(strategy.get(i)); // 输出当前策略列表中的水果名称
}
}
}