您如何看待针对该酒店问题的算法？

一尘不染

您如何看待针对该酒店问题的算法？

algorithm

我在编程课程中正在解决一个问题，但在开发适合该问题的算法时遇到了麻烦。这里是：

你要长途旅行。您从0英里处的公路开始。一路上有n家酒店，在a1 <a2 <…
<an英里的公路上，其中每个ai都是从起点开始测量的。您只能在这些酒店停车，但您可以选择在哪家酒店停车。您必须在目的地的最后一家酒店停留（距离an）。理想情况下，您希望每天旅行200英里，但这可能是不可能的（取决于酒店的间隔）。如果您一天旅行x英里，则该天的罚款为（200-x）^
2。您想要计划行程，以使总罚款，即在所有旅行日中的每日罚款总和最小。给出一种有效的算法，该算法可以确定要停止的酒店的最佳顺序。

因此，我的直觉告诉我要从后面开始，检查惩罚值，然后以某种方式使它们向前匹配（导致O（n ^ 2）运行时，这对于这种情况是最佳的）。

有人看到使这个想法变得可行的任何可能方法，或者对可能的实现有任何想法吗？

阅读 179

2020-07-28

共1个答案

一尘不染

如果x是标记号，ax是到达该标记的里程，并且px是到达该标记的最低罚款，那么如果您之前知道所有标记，则可以计算pn该标记。n``pm``m``n

要将calculate 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。

编辑：使用OP注释中的示例切换到Java代码。请注意，这没有第二段中描述的优化检查。

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

2020-07-28