编辑代码

import java.util.Arrays;
import java.util.LinkedList;


public class Backpack {
     public static LinkedList<Item> stealObject(int packCapacity, Item[] items) {
        int rowCount = items.length + 1;
        int colCount = packCapacity + 1;
        int[][] dpArray = new int[rowCount][colCount];
        LinkedList<Item> objectStolen = new LinkedList<Item>();

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


        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];
                }
                
            }
        }


        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("故宫", 7, 1),
                new Item("颐和园", 8, 2),
                new Item("长城", 9, 3),
                new Item("天坛", 6, 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);

	}

}

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;
    }
}