编辑代码

import java.util.LinkedList;

public class Knapsack {
    public static void stealObjects(int packCapacity, Item[] items, int curItemIndex, int[] path, LinkedList<Item> objectsStolen) {
        if (curItemIndex == items.length) {
            objectsStolen.clear();
            for (int index = 0; index < path.length; ++index) {
                if (path[index] > 0) {
                    objectsStolen.add(items[index]);
                }
            }
            return;
        }

        // 当前的最佳解
        int maxValue = 0;
        for (int i = 0; i < objectsStolen.size(); ++i) {
            maxValue += objectsStolen.get(i).value;
        }

        // 当前已选的价值和重量
        int curValue = 0;
        int curWeight = 0;

        for (int i = 0; i < curItemIndex; ++i) {
            if (path[i] > 0) {
                curValue += items[i].value;
                curWeight += items[i].weight;
            }
        }

        // 放入当前物体
        // 保证物体是能够放入，方案是可行的
        if (items[curItemIndex].weight <= packCapacity - curWeight) {
            path[curItemIndex] = 1;
            // 当前节点的边界值
            int upperValue = curValue + items[curItemIndex].value;
            if (curItemIndex < items.length - 1) {
                Item nextItem = items[curItemIndex + 1];
                upperValue += (packCapacity - curWeight - items[curItemIndex].weight) * (nextItem.value / nextItem.weight);
            }

            // 边界值能超越当前最佳解
            if (upperValue > maxValue) {
                stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen);
            }
        }

        // 不放入当前物体
        path[curItemIndex] = 0;
        // 当前最佳解
        maxValue = 0;
        for (int i = 0; i < objectsStolen.size(); ++i) {
            maxValue += objectsStolen.get(i).value;
        }

        // 当前节点的边界值
        int upperValue = curValue;
        if (curItemIndex < items.length - 1) {
            Item nextItem = items[curItemIndex + 1];
            upperValue += (packCapacity - curWeight) * (nextItem.value / nextItem.weight);
        }

        // 边界值能超越当前最佳解
        if (upperValue > maxValue) {
            stealObjects(packCapacity, items, curItemIndex + 1, path, objectsStolen);
        }
    }

    public static void main(String[] args) {
        // Define your items
        Item[] items = {
                new Item(3000, 4),
                new Item(2000, 3),
                new Item(1500, 1)
        };

        // Set the capacity of the backpack
        int packCapacity = 4;

        // Initialize path array and objectsStolen list
        int[] path = new int[items.length];
        LinkedList<Item> objectsStolen = new LinkedList<>();

        // Call the function to find the optimal solution
        stealObjects(packCapacity, items, 0, path, objectsStolen);

        // Display the stolen objects and their total value
        int totalValue = 0;
        for (Item item : objectsStolen) {
            System.out.println("Stolen: " + item);
            totalValue += item.value;
        }

        System.out.println("Total Value: " + totalValue);
    }
}

class Item {
    int value;
    int weight;

    public Item(int value, int weight) {
        this.value = value;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Value: " + value + ", Weight: " + weight;
    }
}