Algorytm zachłanny czy programowanie dynamiczne?

spamgolden napisał(a):

a więc dla podanych w przykładzie wartości

• dla hotelu nr1.(100). mamy tylko jedną możliwość dostania się. trzeba zapłacić 54.
  -dla hotelu nr2.(120). najtaniej będzie jak bez postoju do niego dojedziemy i zapłacimy 70.
  -dla hotelu nr3(400), najtaniej będzie jak bez postaju dojedziemy. zapłacimy 17.
• dla hotelu nr4(700), najtaniej będzie jak bezpośrednio dojedziemy z początku. zapłacimy 38.
  -dla hotelu nr5(1000). bierzemy pod uwagę tylko poprzednie hotele ktore są w odległości nie większej niż 800, i bierzemy minimum. więc najlepiej będzie jak zatrzymamy się w hotelu nr3 i dojedziemy do nr5. cena to 17+25=42.
  -dla hotelu nr6(1200), analogicznie. warunek spełniają hotele nr3, nr4, nr5. najoptymalniej bierzemy hotel nr3. więc 17+18=35.
  -dla hotelu nr7(1440), warunek spełniają hotele nr4, nr5, nr6. bierzemy minimum, czyli 35+40=75.
  -dla końca- wrunek spełniają hotele nr6 i nr7. bierzmy minimum, czyli 35+0=35.

co o tym sądzisz?
Jest w porządku.

Dla każdego hotelu będzemy trzymac tablice, która powie nam jaki jest minimalny koszt dotarcia do tego hotelu przy ograniczeniach w zadaniu. Algorytm: Dla każdego hotelu w kolejności rosnącej odległości od początku przeglądamy poprzednie hotele które są w promieniu d. Bierzemy minimum z tych hoteli i dodajemy do kosztu aktualnie przetwarzanego hotelu.

Czarny Pomidor napisał(a):

spamgolden napisał(a):

a więc dla podanych w przykładzie wartości

• dla hotelu nr1.(100). mamy tylko jedną możliwość dostania się. trzeba zapłacić 54.
  -dla hotelu nr2.(120). najtaniej będzie jak bez postoju do niego dojedziemy i zapłacimy 70.
  -dla hotelu nr3(400), najtaniej będzie jak bez postaju dojedziemy. zapłacimy 17.
• dla hotelu nr4(700), najtaniej będzie jak bezpośrednio dojedziemy z początku. zapłacimy 38.
  -dla hotelu nr5(1000). bierzemy pod uwagę tylko poprzednie hotele ktore są w odległości nie większej niż 800, i bierzemy minimum. więc najlepiej będzie jak zatrzymamy się w hotelu nr3 i dojedziemy do nr5. cena to 17+25=42.
  -dla hotelu nr6(1200), analogicznie. warunek spełniają hotele nr3, nr4, nr5. najoptymalniej bierzemy hotel nr3. więc 17+18=35.
  -dla hotelu nr7(1440), warunek spełniają hotele nr4, nr5, nr6. bierzemy minimum, czyli 35+40=75.
  -dla końca- wrunek spełniają hotele nr6 i nr7. bierzmy minimum, czyli 35+0=35.

co o tym sądzisz?

Jest w porządku.*

Dla każdego hotelu będzemy trzymac tablice, która powie nam jaki jest minimalny koszt dotarcia do tego hotelu przy ograniczeniach w zadaniu. Algorytm: Dla każdego hotelu w kolejności rosnącej odległości od początku przeglądamy poprzednie hotele które są w promieniu d. Bierzemy minimum z tych hoteli i dodajemy do kosztu aktualnie przetwarzanego hotelu.

Czyli formalnie to będzie zależność rekurencyjna:
Z(n)=MIN(Z(n-1)+Cn,Z(n-2)+Cn,...,Z(n-k)+Cn)
dla Dn<=Dk+800

gdzie Z(n)- najtańsza droga z noclegami do hotelu o numerze n.
Cn- cena noclegu n tego hotelu.
Dn-odległość n-tego hotelu.

spamgolden napisał(a):

Czyli formalnie to będzie zależność rekurencyjna:
Z(n)=MIN(Z(n-1)+Cn,Z(n-2)+Cn,...,Z(n-k)+Cn)
dla Dn<=Dk+800

gdzie Z(n)- najtańsza droga z noclegami do hotelu o numerze n.
Cn- cena noclegu n tego hotelu.
Dn-odległość n-tego hotelu.

Tak, załapałeś. Rzecz ekstra to nie potrzebujesz dodatkowej pamięci, możesz wykorzystać tablicę którą masz na wejściu:)