Если 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