编辑代码

public class Main {
    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;
        
        result = backpack(packCapacity, items, itemCount);
        
        assert result != null;
        if (result.value > 0) {
            System.out.println("最大值为 " + result.value);
            Item item = result.head.next;
            Item prev;
            System.out.print("背包里有 ");
            while (item != null) {
                System.out.print(item.name + ", ");
                prev = item;
                item = item.next;
                prev = null;
            }
            System.out.println();
        }
        
        result.head = null;
        result = null;
    }
    
    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("包容量e " + packCapacity + " 是否少于物品的最小重量\n" +
                    "\n " + minWeight);
            return null;
        }
        
        Result[][] dpArray = new Result[itemCount][packCapacity + 1];
        
        for (int i = 0; i < itemCount; ++i) {
            for (int j = 0; j < packCapacity + 1; ++j) {
                dpArray[i][j] = 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 + 1; ++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;
                }
                
                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 + 1; ++j) {
                dpArray[i][j].head = null;
            }
        }
        
        return result;
    }
    
    
}