编辑代码

package dynamicprogramming;
import java.util.Arrays;
import java.util.LinkedList;



public class Travel {
     // 旅行的方法
     // 输入：travelDayCount: 旅行的天数
     //      places： 景点
     // 输出：准备去的景点
     public static LinkedList<Place> travelPlaces(double[] days, Place[] places) {
        // 1. 找出子问题，确定表格的行和列
        int rowCount = places.length + 1;
        int colCount = days.length;
        // 2. 构建存储子问题的表格
        int[][] dpArray = new int[rowCount][colCount];
        LinkedList<Place> placesToTravel = new LinkedList<Place>(); // 记录需要偷的东西

        //表格清零
        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 (places[i-1].day <= days[j]){
                    // 当前行对应的物品可以放入背包
                    double leftDay = days[j] - places[i - 1].day;
                    
                    dpArray[i][j] = Math.max(places[i-1].score + dpArray[i - 1][(int)(leftDay * 2)], 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]) {
                // 当前行对应的物品被放入包包
                placesToTravel.addFirst(places[i-1]);
                double leftDay = days[j] - places[i - 1].day;
                j = (int)(leftDay * 2);
                i = i-1; // 去掉当前物品
            }
            else {
                // 当前行对应的物品不被放入包包
                i = i - 1;// 去掉当前物品
            }
        }

        return placesToTravel;
    }

	public static void main(String[] args) {
        double[] days = {0, 0.5, 1, 1.5, 2, 2.5, 3, 3.5, 4};
        Place[] places = {
            new Place("故宫", 1, 7),
            new Place("颐和园", 2, 8),
            new Place("长城", 3, 9),
            new Place("天坛", 1, 6)
        };

        LinkedList<Place> objectInPack = travelPlaces(days, places);

        int maxValue = 0;

        System.out.println("去了以下地点：");
        for (int i = 0; i < objectInPack.size(); ++i) {
            maxValue += objectInPack.get(i).score;
            System.out.println(objectInPack.get(i).name);
        }

        System.out.println("总价值：" + maxValue);
	}

}

// 定义物品
class Place {
    public String name;
    public double day;
    public int score;

    Place(String n, double d, int s) {
        this.name = n;
        this.day = d;
        this.score = s;
    }
}