编辑代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

class Item {
    //名称
    public String name;
    //价值
    public int value;
    //重量
    public int weight;
    // 价值重量比
    public double ratio; 

    Item(String name, int value, int weight) {
        this.name = name;
        this.value = value;
        this.weight = weight;
        this.ratio = (double) value / weight;
    }

    // 获取价值重量比
    public double getRatio() {
        return ratio;
    }

    static int maxValue = 0;
    static LinkedList<Item> bestSolution = new LinkedList<>();

    public static void stealObjects(int packCapacity, Item[] items, int curItemIndex, int[] path, LinkedList<Item> objectsStolen, int curWeight, int curValue) {
        // 检查是否已经遍历完所有物品，达到递归的终止条件
        if (curItemIndex == items.length) {
        // 在遍历完所有物品后，检查当前组合的总价值是否超过已知的最大价值
        if (curValue > maxValue) {
        // 如果当前组合的总价值更大，更新最优解
        bestSolution.clear();
        bestSolution.addAll(objectsStolen);
        maxValue = curValue;
        }
        // 结束当前递归分支
        return;
        }
        // 当前节点的边界值
        int upperValue = curValue;
        int remainingCapacity = packCapacity - curWeight;

        for (int i = curItemIndex; i < items.length; i++) {
            if (items[i].weight <= remainingCapacity) {
                upperValue += items[i].value;
                remainingCapacity -= items[i].weight;
            } else {
                upperValue += (remainingCapacity / items[i].weight) * items[i].value;
                break;
            }
        }

        if (upperValue <= maxValue) {
            return; // 剪枝，不再继续探索该分支
        }

        // 放入当前物体
        if (items[curItemIndex].weight <= packCapacity - curWeight) {
            path[curItemIndex] = 1;
            objectsStolen.add(items[curItemIndex]);
            stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen, curWeight + items[curItemIndex].weight, curValue + items[curItemIndex].value);
            objectsStolen.removeLast();
        }

        // 不放入当前物体
        path[curItemIndex] = 0;
        stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen, curWeight, curValue);
    }

    public static LinkedList<Item> solveKnapsackProblem(int packCapacity, Item[] items) {
        LinkedList<Item> objectsStolen = new LinkedList<>();
        int[] path = new int[items.length];

        // 按照价值重量比从高到低进行排序
        Arrays.sort(items, Comparator.comparingDouble(Item::getRatio).reversed());

        stealObjects(packCapacity, items, 0, path, objectsStolen, 0, 0);
        return bestSolution;
    }

    public static void main(String[] args) {
        Item[] items = {
                new Item("IPhone", 2000, 1),
                new Item("吉他", 1500, 1),
                new Item("笔记本电脑", 2000, 3),
                new Item("音箱", 3000, 4)
        };

        LinkedList<Item> objectsStolen = solveKnapsackProblem(4, items);
        int totalValue = 0;

        System.out.println("偷了如下物品：");
        for (Item item : objectsStolen) {
            totalValue += item.value;
            System.out.println(item.name);
        }

        System.out.println("总价值：" + totalValue);
    }
}