编辑代码

import java.util.LinkedList;

public class Backpack {
    
    public static class Item {
        public String name; //物品名称
        public int value;   //物品价值
        public int weight;  //物品重量

    public Item(String n, int v, int w) {   //用于初始化物品名称、价值和重量。
            this.name = n;
            this.value = v;
            this.weight = w;
        }
    }


    // 方法：实现背包问题，返回被偷的物品链表
    public static LinkedList<Item> stealObject(int packCapacity, Item[] items) {
        int numItems = items.length; //获取可偷窃物品数组的长度。

        // 创建一个二维数组来保存最大价值
        int[][] dp = new int[numItems + 1][packCapacity + 1];

        // 动态规划计算最大价值
        for (int i = 1; i <= numItems; i++) {
            for (int j = 1; j <= packCapacity; j++) {
                if (items[i - 1].weight <= j) {
                    // 若当前物品的重量小于等于剩余容量，则可以选择装入背包，比较装入和不装入背包的最大价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - items[i - 1].weight] + items[i - 1].value);
                } else {
                    // 若当前物品的重量大于剩余容量，则无法装入背包，最大价值为上一个物品的最大价值
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        // 回溯找出被偷的物品
        LinkedList<Item> objectInPack = new LinkedList<>();
        int i = numItems;
        int j = packCapacity;
        while (i > 0 && j > 0) {
            if (dp[i][j] != dp[i - 1][j]) {
                // 若当前物品被装入背包，则将该物品加入链表，并减去对应的重量
                objectInPack.addFirst(items[i - 1]);
                j -= items[i - 1].weight;
            }
            i--;
        }

        return objectInPack;
    }

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

        LinkedList<Item> objectInPack = stealObject(4, items);

        int maxValue = 0;

        System.out.println("偷了如下物品：");
        for (int i = 0; i < objectInPack.size(); ++i) {
            maxValue += objectInPack.get(i).value;
            System.out.println(objectInPack.get(i).name);
        }

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

    public static void main(String[] args) {
        test();
    }
}