由网友(听说卸妆是场谋杀)分享简介：有一个问题我工作的一个编程课程，我有麻烦开发一个算法，以适应问题。在这里，它是：There is a problem I am working on for a programming course and I am having trouble developing an algorithm to suit the...

有一个问题我工作的一个编程课程，我有麻烦开发一个算法，以适应问题。在这里，它是：

There is a problem I am working on for a programming course and I am having trouble developing an algorithm to suit the problem. Here it is:

您打算长途旅行。你开始在路上，在一英里后0一路上有n   酒店，在一英里的帖子A1中A2＆LT; ...＆LT;一个，其中每个AI从起点测量的。该   只有你被允许停车的地方是在这些酒店，但您可以选择的酒店   你停在。您必须停止在最后酒店（距离为一个），这是你的目的地。   你理想想行驶200英里天，但是这可能是不可能的（取决于该间距   的酒店）。如果你在一天行程X英里，则判为这天是（200 - X）^ 2。你想   计划您的行程，以便尽量减少总的处罚也就是总和，在所有的旅行天，的   每天处罚。   给出一个高效的算法来决定酒店的最优顺序处停下来。

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）运行时，这是最佳不够的情况）。

So, my intuition tells me to start from the back, checking penalty values, then somehow match them going back the forward direction (resulting in an O(n^2) runtime, which is optimal enough for the situation).

任何人看到任何可能的方式来实现这一设想出，或有任何想法可能implmentations？

Anyone see any possible way to make this idea work out or have any ideas on possible implmentations?

推荐答案

如果 X 是一个标记号，斧是里程的标记， PX 的最低刑罚，以获得该标志，就可以计算出 PN 对于标记 N 如果你知道时的所有标记 M 前 N 。

If x is a marker number, ax is the mileage to that marker, and px is the minimum penalty to get to that marker, you can calculate pn for marker n if you know pm for all markers m before n.

要计算 PN ，找到最小时许+（200 - （一 - 我））^ 2 所有标记 M ，其中 AM＆LT;一个和（200 - （一 - AM））^ 2 小于你对目前最好的 PN （最后一部分是优化）。

To calculate pn, find the minimum of pm + (200 - (an - am))^2 for all markers m where am < an and (200 - (an - am))^2 is less than your current best for pn (last part is optimization).

有关起始标记 0 ， A0 = 0 和 P0 = 0 ，用于标记 1 ， P1 =（200 - A1）^ 2 。随着中启动信息，你可以计算出 P2 ，然后 P3 等多达 PN 。

For the starting marker 0, a0 = 0 and p0 = 0, for marker 1, p1 = (200 - a1)^2. With that starting information you can calculate p2, then p3 etc. up to pn.

修改：切换到Java code，使用来自OP的评论的例子。注意，这不具有在第二段落中描述的优化检查

edit: Switched to Java code, using the example from OP's comment. Note that this does not have the optimization check described in second paragraph.

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