编辑代码

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;
            }
        }
    }
}