您如何看待为此酒店问题开发算法？

Question

我正在编写一个编程课程的问题,我在开发算法以解决问题时遇到了麻烦.这里是:

你要去长途旅行.你开始在0英里处的路上.沿途有n个酒店,在英里的位置a1 <a2 <... <an,其中每个ai都是从起点开始测量的.您可以停止的唯一地点是这些酒店,但您可以选择您停在哪家酒店.您必须在最终的酒店(距离a)停留,这是您的目的地.理想情况下,您希望每天行驶200英里,但这可能无法实现(取决于酒店的间距).如果您在一天内行驶x英里,则当天的罚款为(200 - x)^ 2.您希望计划行程,以便将每日罚款的总罚款(即所有旅行天数的总和)降至最低.提供一种有效的算法,确定要停止的酒店的最佳顺序.

所以,我的直觉告诉我从后面开始,检查惩罚值,然后以某种方式匹配它们返回前进方向(导致O(n ^ 2)运行时,这对于情况是最佳的).

任何人都可以看到任何可能的方法来使这个想法成为现实或对可能的实施有任何想法？

Answer 1

如果x是标记号,ax是该标记的里程数,并且px是达到该标记的最小惩罚,如果您知道之前的所有标记,则可以计算pn标记.npmmn

要计算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 

Answer 2

看起来你可以通过动态编程来解决这个问题.子问题如下:

d(i):从开始到酒店旅行的最低罚款i.

递归公式如下:

d(0) = 0 其中0是起始位置.

d(i) = min_{j=0, 1, ... , i-1} ( d(j) + (200-(ai-aj))^2)

到达酒店的最低罚款i是通过尝试前一天的所有停靠位置,添加今天的罚款并采取最低限度的罚款.

为了找到路径,我们存储在一个单独的数组(路径[])中,我们必须从哪个酒店出发,以达到该特定酒店的最低罚款.通过向后遍历数组(从路径[n]),我们获得路径.

运行时为O(n ^ 2).