Naloga: 0-1 nahrbtnik (dinamično programiranje)

Iz MaFiRaWiki

Z uporabo dinamičnega programiranja sprogramiraj algoritem, ki reši problem 0-1 nahrbtnika. Požrešna metoda namreč ne vrne optimalne rešitve (pri preprostem nahrbtniku pa je vrnila optimalno rešitev).


Algoritem:

  • Na vsakem koraku se odlocimo ali damo predmet v nahrbtnik.
  • Pravilo optimalnosti velja.
  • Definiramo g[i,W] kot vrednost optimalne resitve, kjer polnimo nahrbtnik velikosti W in smo upostevali predmete z indeksi ≤ i.
    Iscemo: g[n,M]
    Vemo:
    g[0,W]/;W≥0:=0
    g[0,W]/;W<0:=-∞ (pri implementaciji uporabimo -999)
    g[n,W]/;W≤0:=0
  • Zanima nas vrednost nahrbtnika (vrednost optimalne resitve) in katere elte vzamemo. Ce imamo dve resitvi z enako ceno, nam je bolj vsec tista z manjsim volumnom.
  • Resujemo od spodaj navzgor:
    S[j] je mnozica parov (Wj,cj), ki predstavljajo resitev nahrbtnika velikosti Wj s ceno cj, kjer smo upostevali elemente od 1 do j.
    Z[j] je mnozica parov (Wj,cj), za katere velja [W-vj, C-cj] ∈ S[j-1]
    S[j+1]=Sj *unija* Zj+1, pri cemer je *unija* operacija, ki v primeru ko imamo dva elementa z isto velikostjo, vzamemo tistega z vecjo ceno (sicer je navadna unija).
    S[0] = {(0,0)}

Rešitev

Glej tudi

Osebna orodja