编辑代码

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


public class Backpack {
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 test() {
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);

    }

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

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

class GreedyItem {
public String name;
public double totalWeight;
public double totalValue;

public GreedyItem(String itemName, double weight, double value) {
this.name = itemName;
this.totalWeight = weight;
this.totalValue = value;
}
public GreedyItem(GreedyItem item) {
this.name = item.name;
this.totalWeight = item.totalWeight;
this.totalValue = item.totalValue;
}
}