package dynamicprogramming;
import java.util.Arrays;
import java.util.LinkedList;
public class Backpack {
public static LinkedList<place> stealObject(int packCapacity, place[] items) {
int rowCount = items.length + 1;
int colCount = packCapacity + 1;
int[][] dpArray = new int[rowCount][colCount];
LinkedList<place> objectStolen = new LinkedList<place>();
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].days <= j){
dpArray[i][j] = Math.max(items[i-1].scores + dpArray[i - 1][j - items[i-1].days], 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].days;
i = i-1;
}
else {
i = i - 1;
}
}
return objectStolen;
}
public static void test() {
place[] items = {
new place("故宫", 7, 1),
new place("颐和园", 8, 2),
new place("长城", 9, 3),
new place("天坛", 6, 1)
};
LinkedList<place> objectInPack = stealObject(4, items);
int maxValue = 0;
System.out.println("景点能够获得最大价值:");
for (place item : objectInPack) {
maxValue += item.scores;
System.out.println(item.name);
}
System.out.println("总评分:" + maxValue);
}
public static void main(String[] args) {
Backpack.test();
}
}
class place {
public String name;
public int scores;
public int days;
public place(String n, int s, int d) {
this.name = n;
this.scores = s;
this.days = d;
}
}