如果
x
是一个标记号,
ax
是到达那个标记的里程数,
px
是到达那个标记的最小惩罚,则可以计算标记
n
的
pn
,如果您知道标记
n
之前的所有标记
m
的
pm
。
要计算
pn
,请查找所有标记
m
的
pm + (200 -(an - am))^ 2
的最小值,其中
am < an
并且
(200-(an-am))^ 2
小于当前
pn
的最佳值(最后一部分是优化)。
对于起始标记
0
,
a0 = 0
和
p0 = 0
,对于标记
1
,
p1 = (200-a1)^2
。有了这些起始信息,您可以计算
p2
、
p3
等,直到
pn
。
编辑:切换为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
{0, 200, 400, 600, 601}
。 - greybeard