import java.util.ArrayList;
import java.util.List;
public class Knapsack {
static class Fruit {
String name;
int weight;
int value;
public Fruit(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
}
public static void main(String[] args) {
List<Fruit> fruits = new ArrayList<>();
fruits.add(new Fruit("苹果", 15, 300));
fruits.add(new Fruit("香蕉", 18, 180));
fruits.add(new Fruit("橘子", 10, 150));
fruits.add(new Fruit("猕猴桃", 9, 270));
int capacity = 20;
int[][] dp = new int[fruits.size() + 1][capacity + 1];
for (int i = 1; i <= fruits.size(); i++) {
Fruit fruit = fruits.get(i - 1);
for (int j = 1; j <= capacity; j++) {
if (fruit.weight > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - fruit.weight] + fruit.value);
}
}
}
int maxValue = dp[fruits.size()][capacity];
System.out.println("20052218 刘嘉源");
System.out.println("装入的总价值:" + maxValue);
System.out.println("装的策略为:");
int remainingCapacity = capacity;
for (int i = fruits.size(); i > 0 && maxValue > 0; i--) {
if (maxValue != dp[i - 1][remainingCapacity]) {
Fruit fruit = fruits.get(i - 1);
System.out.println(fruit.name);
maxValue -= fruit.value;
remainingCapacity -= fruit.weight;
}
}
}
}