Jedziemy samochodem o pojemności baku W. Znamy rozkład stacji benzynowych przy drodze - każda z nich znajduje się na pełnym kilometrze drogi oraz na stacji numer x cena wynosi w(x). Pokaż algorytm minimalizujący koszt paliwa podczas jazdy do końca drogi (czyli stacji numer n).
Jak do takiego zadania się zabrać? Czego w ogóle tutaj użyć?
Może zbudować drzewo ze wszystkimi możliwościami, przeszukać je w głąb i zapamiętać najbardziej optymalną drogę? Jeśli nie ma powrotów do poprzednich stacji, to rozwiązanie nie będzie skomplikowane. Możliwe, że można to zrobić z użyciem rekurencji, bez drzewa.
Programowanie dynamiczne dp[numerStacji][paliwoDostępneWBaku] = minimalnyKoszt. Przy naiwnej implementacji wyjdzie coś w stylu O(liczbaStacji^2 * pojemnośćBaku), powinno się to trochę amortyzować, gdy stacje nie są blisko siebie.
Pewnie czegoś nie zrozumiałem, ale czy nie jest tu potrzebne zużycie paliwa?
Ale pytasz o moje rozwiązanie? Jak tak, to zużycie jest ukryte w koszcie.
Zużycie paliwa jest jakąś stałą, pewnie 1l==1km, ale nie jest zbyt istotne z punktu widzenia algorytmu.
Też widzę to dynamicznie, tyle że bez trzymania informacji o tym ile mamy paliwa dostępnego w baku.W danym punkcie zawsze chcemy mieć już pusty bak i patrzymy w przeszłość gdzie nam się najbardziej opłaca zatankować by do niego dojechać.
for numerStacji = 0 to n
{
var minimum = +inf;
for i = 1 to W
{
var koszt = minimlanyKoszt[numerStacji - i] + w(numerStacji - i) * i;
minimum = min(minimum, koszt);
}
minimalnyKoszt[numerStacji] = minimum;
}
i złożoność będzie liniowa, bo W pewnie jest jakąś małą stałą.
Edytka:
@Afish ma rację, moje założenie o pustym baku było błędne, i kontrprzykład można znaleźć bardzo prosto w(i)= 1, 2, 15, 15, 0 dla W = 3
poprawny scenariusz to zatankować w pierwszej 3x1 i do tankować 1x2 co daje nam łączny koszt 5
a moje rozwiązanie zwróci kosz 1x1 +3x2 ==7
także to nie jest poprawna odpowiedź