public class BackpackFruitGame {
public static void main(String[] args) {
String[] fruits = {"苹果", "香蕉", "橘子", "猕猴桃"};
int[] weights = {15, 18, 10, 9};
int[] values = {300, 180, 150, 270};
int capacity = 20;
int n = fruits.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
if (weights[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
}
}
}
System.out.println("背包中的最大价值:" + dp[n][capacity]);
int remainingCapacity = capacity;
for (int i = n; i > 0 && remainingCapacity > 0; i--) {
if (dp[i][remainingCapacity] != dp[i - 1][remainingCapacity]) {
System.out.println("选择水果:" + fruits[i - 1] + ",重量:" + weights[i - 1] + "kg,价值:" + values[i - 1] + "元");
remainingCapacity -= weights[i - 1];
}
}
}
}