编辑代码

package dynamicprogramming;
import java.util.LinkedList;

//定义地方类
class LocationItem {
    public String location;//地点名称
    public int score;//评分
    public int time;//时间
    LocationItem(String location, int score, int time) {//构造方法
        this.location = location;
        this.score = score;
        this.time = time;
    }
}

public class Journey {
    //旅程最优化问题
    //输入：days：旅程天数    items:可以去的地方
    //输出：选择去的地方的集合
    public static LinkedList<LocationItem> journey(int days, LocationItem[] items) {
        //1.找出子问题，确定表格的行和列
        int row = days + 1;
        int col = items.length + 1;
        LinkedList<LocationItem> chooseLocation = new LinkedList<>();     //用一个列表记录选择去的地方
        //2.表格清零
        int[][] cell = new int[row][col];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                cell[i][j] = 0;
            }
        }
        //3.利用公式（Max( items[i-1].score +cell[i-1][j-items[i-1].time], cell[i-1][j] ）填充动态规划表
        for(int i = 1; i < row; i++) {
            for(int j = 1; j < col; j++) {
                if (items[i - 1].time <= j) {
                    // 当前行对应的地点可以加入行程
                    cell[i][j] = Math.max((items[i-1].score + cell[i-1][j-items[i-1].time]), cell[i-1][j]);
                } else {
                    // 当前行对应的地点不可以加入行程
                    cell[i][j] = cell[i-1][j];
                }
            }
        }
        System.out.println(cell);
        
        //4.利用表格找出选择去的地方
        int i = row - 1;
        int j = col - 1;
        while (i > 0 && j > 0) {
            if (cell[i][j] != cell[i - 1][j]) { //从动态规划表右下角开始，如果当前动态规划表的i行j列与上一行的值不一致，则说明当前i行的地点有加入行程
                chooseLocation.addFirst(items[i - 1]);//当前行对应的地点加入行程
                j = j - items[i - 1].time;//减去当前地点花费的时间
                i = i - 1;//去掉当前地点
            } else {
                //当前行对应的地点不加入行程
                i = i - 1;//去掉当前地点
            }
        }

        return chooseLocation;//返回选择去的地方的列表
    }

    public static void test() {
        LocationItem[] items = {
            new LocationItem("故宫", 7, 1),
            new LocationItem("颐和园", 8, 2),
            new LocationItem("长城", 9, 3),
            new LocationItem("天坛", 6, 1)
        };
        LinkedList<LocationItem> chooseLocation = journey(4, items);

        int maxValue = 0;//定义一个存放总评分的变量

        System.out.println("旅程如下：");
        for (int i = 0; i < chooseLocation.size(); ++i) {
            maxValue += chooseLocation.get(i).score;
            System.out.println(chooseLocation.get(i).location + " 评分："+ chooseLocation.get(i).score);
        }
        System.out.println("总评分：" + maxValue);
    }
    public static void main(String[] args) {
        test();
    }
}