Naloga: 01 nahrbtnik s sestopanjem

Iz MaFiRaWiki

Imamo majhen nahrbtnik volumna V ter n predmetov velikosti vi in cen ci, ki bi jih radi dali v nahrbtnik. Predmet lahko damo v nahrbtnik cel ali pa sploh ne:

  • če je xi = 1, i-ti predmet je v nahrbtniku
  • če je xi = 0, i-ti predmet ni v nahrbtniku

Iščemo tako razporeditev xi, da bo vsota \Sigma_{i=1}^{n} c_i x_i največja možna, ob pogoju \Sigma_{i=1}^{n}v_i x_i \le V.


Sprogramiraj problem 0-1 nahrbtnik s sestopanjem.

Rešitev

Glej tudi

Osebna orodja