algorithm - 您如何看待为这个酒店问题开发算法？

Question

我正在为一门编程类(class)解决一个问题，但我无法开发出适合该问题的算法。在这里:

You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < ... < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. You'd ideally like to travel 200 miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is (200 - x)^2. You want to plan your trip so as to minimize the total penalty that is, the sum, over all travel days, of the daily penalties. Give an efficient algorithm that determines the optimal sequence of hotels at which to stop.

所以，我的直觉告诉我从后面开始，检查惩罚值，然后以某种方式匹配它们返回正向(导致 O(n^2) 运行时间，这对于这种情况来说已经足够了)。

有人看到任何可能的方法来实现这个想法或对可能的实现有任何想法吗？

Answer 1

如果x是标记编号，ax是到那个标记的里程数，px是到达那个标记的最小惩罚，你可以计算pn用于标记 n如果你知道pm对于所有标记 m之前n .

计算pn , 找到 pm + (200 - (an - am))^2 的最小值对于所有标记 m其中 am < an和 (200 - (an - am))^2低于您目前最好的 pn (最后一部分是优化)。

对于起始标记 0 , a0 = 0和 p0 = 0 , 用于标记 1 , p1 = (200 - a1)^2 .使用该起始信息，您可以计算出 p2 , 然后 p3等直到pn .

edit:切换到 Java 代码，使用 OP 评论中的示例。请注意，这没有第二段中描述的优化检查。

public static void printPath(int path[], int i) {
    if (i == 0) return;
    printPath(path, path[i]);
    System.out.print(i + " ");
}

public static void main(String args[]) {
    int hotelList[] = {0, 200, 400, 600, 601};
    int penalties[] = {0, (int)Math.pow(200 - hotelList[1], 2), -1, -1, -1};
    int path[] = {0, 0, -1, -1, -1};
    for (int i = 2; i <= hotelList.length - 1; i++) {
        for(int j = 0; j < i; j++){
            int tempPen = (int)(penalties[j] + Math.pow(200 - (hotelList[i] - hotelList[j]), 2));
            if(penalties[i] == -1 || tempPen < penalties[i]){
                penalties[i] = tempPen;
                path[i] = j;
            }
        }
    }
    for (int i = 1; i < hotelList.length; i++) {
        System.out.print("Hotel: " + hotelList[i] + ", penalty: " + penalties[i] + ", path: ");
        printPath(path, i);
        System.out.println();
    }
}

输出是:

Hotel: 200, penalty: 0, path: 1 
Hotel: 400, penalty: 0, path: 1 2 
Hotel: 600, penalty: 0, path: 1 2 3 
Hotel: 601, penalty: 1, path: 1 2 4