Preprosti problem nahrbtnika

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka MonikaDraškovič.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Problem preprostega nahrbtnika

To je en izmed problemov na katerega pogosto naletimo v vsakdanjem življenju. Iz izkušenj vemo, da če bi polnili nahrbtnik s predmeti po vrsti, kot nam pridejo pod roko, hitro česa zelo pomembnega ne bi dali not. Prav tako, če bi vse predmete najprej uredili po njihovi pomembnosti, bi se hitro zgodilo, da bi v nahrbtnik dali predmet, ki je sam po sebi pomemben, zasede pa toliko prostora, da bi dali namesto njega druga dva, ki sta skupaj bolj pomembna.
Požrešna metoda je en izmed načinov za reševanje problema preprostega nahrbtnika, kjer združimo oba kriterija in na vsakem koraku vzamemo tisti predmet, ki ima največjo relativno vrednost (pomembnost na enoto prostornine) ci / vi.


Imamo nahrbtnik prostornine V in n predmetov, ki bi jih radi dali v nahrbtnik. Pri tem je:

  • vi... velikost posameznega predmeta za katerega velja 0 < vi ≤ V
  • ci... vrednost (cena oz. kako pomembno je, da predmet vzamemo s sabo) posameznega predmeta, kjer je ci > 0.

Po predpostavki, da predmete lahko režemo, iščemo razporeditev xi, (i = 1,2,...,n) z deleži med 0 in 1, ki nam pove, koliko vzamemo i-tega predmeta. Veljati mora še:

  • \sum_{i=0}^{n} \ v_{i} \ x_{i}V... velikost nahrbtnika
  • max\sum_{i=0}^{n} \ c_{i} \ x_{i}... maksimalna skupna vrednost razporeditve

Vrednost nahrbtnika je vsota vrednosti deležev predmetov, ki so v nahrbtniku.

Algoritem

Predmeti morajo biti vnaprej urejeni po relativni vrednosti \frac{c[i]}{v[i]} \ge \frac{c[i+1]}{v[i+1]} ; i=1,2, ..., n, od največje do najmanjše vrednosti. Tako urejene predmete jemljemo po vrsti, dokler gredo celi v nahrbtnik. Ko naletimo na prvega takega, da ne gre več cel v nahrbtnik, vzamemo tolikšen delež tega predmeta, da nahrbtnik napolnimo.

  1. napolni (int V, int n, int[] v, int[] c, int[] x){
  2.  
  3. //V... prostornina nahrbtnika
  4. //n... število predmetov
  5. //v... velikost predmeta
  6. //c... vrednost predmeta
  7. //x[i], i = 1,...,n, 0 ≤ x[i] ≤ 1, rešitev, ki
  8. // optimizira vrednost vseh predmetov v nahrbtniku.
  9. //Predmeti morajo biti vnaprej urejeni po relativni vrednosti:
  10. //c[i]/v[i] >= c[i+1]/v[i+1], i=1,...,n-1
  11.  
  12. //na začetku je rešitev prazna
  13. for(int i = 1; i <= n; i++){
  14. x[i] = 0;
  15. }
  16. int prostor = V;
  17. int stevec;
  18. //pregledamo vse predmete
  19. for(int i = 1; i <= n; i++){
  20. if(v[i] > prostor){
  21. stevec = i;
  22. break;
  23. }
  24. else{
  25. //i-ti predmet še gre v nahrbtnik
  26. x[i] = 1;
  27. prostor = prostor - v[i];
  28. stevec = i;
  29. }
  30. }
  31. //izračunamo delež predmeta, ki še gre v nahrbtnik
  32. //ostali dobijo vrednost 0, ker ne gredo več v nahrbtnik
  33. while(stevec <= n){
  34. x[stevec] = prostor / v[stevec];
  35. stevec++;
  36. }
  37. }

Primer

Imamo nahrbtnik prostornine V = 20 in 6 predmetov določene velikosti in vrednosti, ki bi jih radi stlačili v nahrbtnik.

  • V = 10 ... volumen
  • c = (1, 2, 10, 5, 6, 2) ... vrednosti predmetov
  • v = (2, 1, 4, 3, 4, 5) ... velikosti predmetov

Izračunajmo relativne vrednosti:
c / v = (0.5, 2, 2.5, 1.67, 1.5, 0.4)
Rešitev(na začetku je 0, ker še nismo izbrali nobenega predmeta):
x = (0, 0, 0, 0, 0, 0)

Po vrsti jemljemo predmete od največje do najmanjše vrednosti:

  • najprej vzamemo 3.predmet → ostane še V = 10 - 4 = 6 prostora
c / v = (0.5, 2, 2.5, 1.67, 1.5, 0.4)
x = (0, 0, 1, 0, 0, 0)
  • sledi 2.predmet → ostane še V = 6 - 1 = 5 prostora
c / v = (0.5, 2, 2.5, 1.67, 1.5, 0.4)
x = (0, 1, 1, 0, 0, 0)
  • sledi 4.predmet → ostane še V = 5 - 3 = 2 prostora
c / v = (0.5, 2, 2.5, 1.67, 1.5, 0.4)
x = (0, 1, 1, 1, 0, 0)
  • sledi 5.predmet → ker pa je V = 2 - 4 < 0, lahko vzamemo samo polovico tega predmeta
c / v = (0.5, 2, 2.5, 1.67, 1.5, 0.4)
x = (0, 1, 1, 1, 0.5, 0)

Rešitev: S sabo vzamemo drugi, tretji, četrti in polovico petega predmeta. Za prvega in šestega pa ni več prostora.

Osebna orodja