编辑代码

public class Main {

    static class Item {
        String name;
        int weight;
        int value;
        Item next;

        Item(String n, int w, int v) {
            name = n;
            weight = w;
            value = v;
            next = null;
        }

        Item() {
            name = "";
            weight = 0;
            value = 0;
            next = null;
        }

        Item(Item item) {
            name = item.name;
            weight = item.weight;
            value = item.value;
            next = item.next;
        }
    }

    static class Result {
        int value;
        Item head;

        Result() {
            value = 0;
            head = new Item();
        }

        Result(Result result) {
            value = result.value;
            head = new Item();
            head.next = result.head.next;
        }
    }

    static Result backpack(int packCapacity, Item[] items, int itemCount) {

        int minWeight = items[0].weight;

        // 找出最小重量，进行健壮性检查
        for (int i = 1; i < itemCount; ++i) {
            int curWeight = items[i].weight;
            if (curWeight < minWeight) {
                minWeight = curWeight;
            }
        }

        if (packCapacity < minWeight) {
            System.out.println("The capacity of package " +
                    packCapacity + " is less than the minimum weight of items " +
                    minWeight);
            return null;
        }

        // 创建表格，横轴是物品，纵轴是包能放入的物品的重量
        Result[][] dpArray = new Result[itemCount][packCapacity + 1];

        // 填充表格
        for (int i = 0; i < itemCount; ++i) {
            for (int w = 0; w <= packCapacity; ++w) {
                dpArray[i][w] = new Result();
            }
        }

        for (int i = 0; i < itemCount; ++i) {
            // 记录放入背包物品的重量和价值
            int curWeight = items[i].weight;
            int curValue = items[i].value;
            for (int w = minWeight; w <= packCapacity; ++w) {
                // 记录不放入当前物品的情况下，放入背包物品能够达到的最大价值
                int preTotalValue = 0;

                if (i > 0) {
                    preTotalValue = dpArray[i - 1][w].value;
                }

                // 记录放入当前物品的情况下，放入背包物品能够达到的最大价值
                int curTotalValue = 0;

                // 如果当前物品能够放入背包，记录下物品的价值
                if (w >= curWeight) {
                    curTotalValue = curValue;
                }
                // 如果放入当前物品后背包还能放入其他物品，且确实还有其他物品，加上剩余的小背包能够放入物品的最大价值
                if (w > curWeight && i > 0) {
                    curTotalValue += dpArray[i - 1][w - curWeight].value;
                    dpArray[i][w].head.next = dpArray[i - 1][w - curWeight].head.next;
                }

                // 找出放入当前物品和不放入当前物品情况下，放入背包的物品能够达到的最大价值
                int maxTotalValue = preTotalValue;

                if (maxTotalValue < curTotalValue) {
                    maxTotalValue = curTotalValue;
                    items[i].next = dpArray[i][w].head.next;
                    dpArray[i][w].head.next = new Item(items[i]);
                } else {
                    dpArray[i][w].head.next = dpArray[i - 1][w].head.next;
                }

                // 记录下放入当前物品后，能够放w磅物品的背包能够放入物品的最大价值
                dpArray[i][w].value = maxTotalValue;
            }
        }

        // 记录下最终的最大结果
        Result result = new Result(dpArray[itemCount - 1][packCapacity]);

        for (int i = 0; i < itemCount; ++i) {
            for (int j = 0; j <= packCapacity; ++j) {
                dpArray[i][j].head = null;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int packCapacity = 4;
        Item[] items = {
                new Item("Guitar", 1, 1500),
                new Item("Sound Equipment", 4, 3000),
                new Item("Notebook", 3, 2000),
                new Item("IPhone", 1, 2000)
        };
        int itemCount = items.length;
        Result result = null;

        result = backpack(packCapacity, items, itemCount);

        if (result.value > 0) {
            System.out.println("Max value is " + result.value);
            Item item = result.head.next;
            Item prev;
            System.out.print("Objects are ");
            while (item != null) {
                System.out.print(item.name + ", ");
                prev = item;
                item = item.next;
                prev = null;
            }
            System.out.println();
        }

        result.head = null;
        result = null;
    }
}