编辑代码

import java.util.ArrayList;
import java.util.List;

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 class TestQiMo{
    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++) {
            for (int j = 1; j <= capacity; j++) {
                if (fruits.get(i - 1).weight > j) {
                    //检查当前水果的重量是否大于当前背包容量。如果是，则当前水果无法放入背包。
                    dp[i][j] = dp[i - 1][j];
                    //如果当前水果无法放入背包，则将上一个水果在同样背包容量下的最优解赋给当前位置的最优解。
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - fruits.get(i - 1).weight] + fruits.get(i - 1).value);
                    //如果当前水果可以放入背包，则比较不放入当前水果和放入当前水果后的最优解，选取较大的价值作为当前位置的最优解
                }
            }
        }
        List<String> strategy = new ArrayList<>();
        List<Integer> maxValue = new ArrayList<>();
        int i = fruits.size();
        int j = capacity;
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                strategy.add(fruits.get(i - 1).name);
                maxValue.add(fruits.get(i - 1).value);
                j -= fruits.get(i - 1).weight;
            }
            i--;
        }

        // 打印出装水果的策略
        System.out.println("策略为：");
        for (int k = strategy.size() - 1; k >= 0; k--) {
            System.out.println(strategy.get(k));
        }
        int totalValue=0;
        for (int k = maxValue.size() - 1; k >= 0; k--) {
            totalValue+=maxValue.get(k);
        }
        System.out.println("最大价值为：");
        System.out.println(totalValue);
    }
}