编辑代码

package homework;
import java.util.Arrays;
import java.util.LinkedList;

public class Backpack {
    // 定义物品
    static class Item {
        String name;
        int value;
        int weight;

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

    // 偷东西的方法
    // 输入：packCapacity：包的容量
    //      items： 可以偷的物品
    // 输出：偷的物品集合
    public static LinkedList<Item> stealObject(int packCapacity, Item[] items) {
        // 1. 找出子问题，确定表格的行和列
        int rowCount = items.length + 1;
        int colCount = packCapacity + 1;
        // 2. 构建存储子问题的表格
        int[][] dpArray = new int[rowCount][colCount];
        LinkedList<Item> objectStolen = new LinkedList<Item>(); // 记录需要偷的东西

        // 表格清零
        for (int i = 0; i < rowCount; ++i) {
            Arrays.fill(dpArray[i], 0);
        }

        // 3. 利用公式（Max(item[i - 1].value + Cell[i-1][j - item[i-1].weight], Cell[i-1][j])）填充动态规划表
        for (int i = 1; i < rowCount; ++i) {
            for (int j = 1; j < colCount; ++j) {

                if (items[i - 1].weight <= j) {
                    // 当前行对应的物品可以放入背包
                    dpArray[i][j] = Math.max(items[i - 1].value + dpArray[i - 1][j - items[i - 1].weight], dpArray[i - 1][j]);
                } else {
                    // 当前行对应的物品不可以放入背包
                    dpArray[i][j] = dpArray[i - 1][j];
                }

            }
        }

        // 4. 利用表格找出要放入包中的物品
        int i = rowCount - 1;
        int j = colCount - 1;
        while (i > 0 && j > 0) {

            if (dpArray[i][j] != dpArray[i - 1][j]) {
                // 当前行对应的物品被放入包包
                objectStolen.addFirst(items[i - 1]);
                j = j - items[i - 1].weight; // 减去放入包的当前物品的重量
                i = i - 1; // 去掉当前物品
            } else {
                // 当前行对应的物品不被放入包包
                i = i - 1;// 去掉当前物品
            }
        }

        return objectStolen;
    }

    public static void main(String[] args) {
        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 (Item item : objectInPack) {
            maxValue += item.value;
            System.out.println(item.name);
        }

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