Izpitno vprašanje RAČ2PRA 15600

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vprašanje

Razloži problem enostavnega nahrbtnika. Navedi tudi praktičen primer!


Odgovor

Imamo majhen nahrbtnik velikosti V (V je prostornina nahrbtnika) ter veliko predmetov, ki jih želimo shraniti v nahrbtnik. Velikost posameznega predmeta je vi (0 < vi ≤ V), cena (vrednost) vsakega predmeta pa je ci (ci > 0). Predpostavimo, da predmete lahko režemo in vrednost rezanega dela je sorazmerna deležu predmeta. Vrednost nahrbtnika je vsota vrednosti deležev predmetov, ki so v nahrbtniku.

  • Za vsak i (za vsak predmet) iščemo razporeditev xi z deleži med 0 in 1‚ ki nam pove, koliko vzamemo i-tega elementa.
Omejitve (dopustni x): \sum_{i=0}^{n} \ v_{i} \ x_{i}V
Optimalni (med dopustnimi x): max\sum_{i=0}^{n} \ c_{i} \ x_{i}


  • Več strategij do rešitve:
    strategija A: vzamemo največ vreden predmet: V = 20, v = (20, 10, 10), c = (10, 9, 9)
    strategija B: vzamemo najmanjši predmet: V = 20, v = (9, 10, 10), c = (1,10,10)

Vendar ti dve strategiji ne vodita k optimalni rešitvi

prava strategija: glede na vrednost je ci / vi


  • Algoritem :

  1. napolni (int V, int n, int[] v, int[] c, int[] x){
  2.  
  3. // V - prostornina nahrbtnika, n - število predmetov, ki jih želimo spraviti v nahrbtnik
  4. // v - velikost predmeta, c - cena(vrednost) predmeta
  5. // napolni poišče rešitev x[i], i = 1,...,n, 0 <= x[i] <= 1, ki optimizira vrednost vseh
  6. // predmetov v nahrbtniku.
  7. // Predmeti morajo biti vnaprej urejeni po relativni vrednosti c[i]/v[i] >= c[i+1]/v[i+1], i=1,...,n-1
  8.  
  9. // na začetku je rešitev prazna
  10. for(int i = 1; i <= n; i++) {
  11. x[i] = 0;
  12. int prostor = V;
  13. }
  14.  
  15. // pregledamo vse predmete
  16. for(int i = 1; i <= n; i++) {
  17. if(v[i] > prostor){
  18. break;
  19. }
  20. else { // i-ti predmet še gre v nahrbtnik
  21. x[i] = 1;
  22. prostor = prostor - v[i];
  23. }
  24. }
  25.  
  26. // v nahrbtnik še del preostalega največ vrednega predmeta
  27. if(int i <= n){
  28. x[i] = prostor / v[i];
  29. }
  30. }
Osebna orodja