Problem ranca
Problem ranca je problem koji je najviše istraživan u kombinatornoj optimizaciji, sa mnogo primena u stvarnom životu. Zbog ovoga je ispitano mnogo specijalnih slučajeva i napravljeno je mnogo generalizacija.

Zajedničko za sve verzije je n predmeta, a svaki predmet  ima pridruženu vrednost pj i težinu wj. Cilj je sakupiti određeni broj predmeta, tako da vrednost ranca bude maksimalna, ali da težina ranca ne pređe zadatu vrednost W. Uglavnom, ovi koeficijenti se skaliraju da bi bili celi brojevi i gotovo uvek se pretpostavlja da su pozitivni.

Problem ranca u osnovnoj formi:

Direktne generalizacije 
Jedna od češćih varijanti je da se svaki predmet može birati više puta. Konkretno, kod problema ograničenog ranca za svaki predmet j, i gornju granicu uj (koja može biti pozitivan ceo broj ili beskonačno) za broj predmeta j može biti izabrano:

Neograničeni problem ranca (koji se nekada naziva i celobrojni problem ranca) ne postavlja gornju granicu za broj predmeta koji mogu da se odaberu: 

Lueker je pokazao 1975. godine  da je varijata bez granice NP-kompletan problem. Obe varijatne, i sa ograničenjem i bez ograničenja, imaju aproskimativnu šemu polinomijalnog vremena - FPTAS (u suštini, kao i kod 0-1 problemna ranca).

Ako se predmeti podele na k klasa označene sa , i ako iz svake klase mora da se uzme tačno jedan predmet, dobija se problem ranca sa višetrukim izborom:

Ako su za sve predmete vrednost i težina identični, dobijamo problem zbira podskupa (često je dat odgovarajući problem, problem odlučivanja ):

Ako imamo n predmeta i m rančeva sa kapacitetima , dobijamo višestruki problem ranca:

Kao specijalan slučaj višetrukog problema ranca, kada su vrednosti jednake težinama i svi binovi imaju isti kapacitet, možemo imati i problem zbira višetrukog podskupa:

Kvadratni problem ranca:

Problem ranca - Unija skupa:

SUKP (Set-Union Knapsack Problem) je definisao Kellerer i dr.:
Dat je skup od  predmeta  i skup od , tako reći, elemenata , gde svaki predmet  odgovara podskupu  skupa elemenata . Predmeti  imaju nenegativne vrednosti , , a elementi  nenegativne težine , . Konačna težina skupa predemeta je data konačnom težinom elemenata unije odgovarajućih skupa elemenata. Cilj je naći podskup predmeta sa konačnom težinom koja ne prelazi kapacitet ranca i maksimalnu vrednost.

Višestruko ograničenje 
Ako postoji više od jednog ograničenja (na primer, i granica za obim i granica za težinu, gde obim i težina svakog predmeta nisu povezani), dobijamo problem ranca sa višestrukim ograničenjem, višedimenzionalni problem ranca, ili m-dimenzionalni problem ranca. (Napomena, "dimenzija" se ovde ne odnosi na oblik predmeta.) Ovo ima 0-1, ograničenu, i neograničenu varijantu; neograničena je prikazana ispod.

Pokazano je da je varijanta 0-1 (za sve fiksne ) NP-komplentna oko 1980. godine i da nema FPTAS osim ako je P=NP.

Ograničena i neograničena varijanta (za sve fiksne ) imaju istu složenost.

Za bilo koje fiksno , ovi problemi imaju pseudo-polinomijalni algoritam (sličan onom za klasičn problem ranca) i PTAS.

Ranac-slični problemi 
Ako su sve vrednosti jednake 1, možemo da pokušamo da minimizujemo broj predmeta koji tačno popunjuju ranac:

Ako imamo broj skladišta (iste veličine), i želimo da spakujemo svih n predmeta u što je manje moguće skladišta, dobijamo bin-problem ranca, koji je urađen tako da ima indikator za varijable  skladište i se trenutno koristi:

 Problem seckanja zaliha je identičan bin-problemu ranca, ali pošto parcijalne istance obično imaju mnogo manje tipova predmeta, često se koristi druga formulacija. Predmet j je potreban Bj puta, svaki primer premdeta koji može da stane u samo jedan ranac ima promenljivu, xi (postoji m primera), i primer i koristi predmet j bij puta:

Ako na višestruki problem ranca, dodamo ograničenje da je svaki podskup veličine n i uklonimo ograničenje za konačnu težinu, dobijamo problem zadatka, koji je takođe problem pronalaženja maksimalnog bipartitivnog poklapanja:

U varijanti ranac maksimalne gustine postoji inicijalna težina , 
i mi uvećavamo gustinu izabranog predemta koi ne ugrožava kapacitet ograničenja:

Iako su manje poznadi od problema pomenutih iznad, postoji još nekoliko ranac-sličnih problema, uključujući:
 Ugneždeni problem ranca
 Kolapsirajući problem ranca
 Nelinearan problem ranca
 Obrnuto-parametarski problem ranca

Od ovih, poslednja tri su obrađena u referencnom radu Kellerer-a i drugih, Knapsack Problems.

Reference

Literatura 
 "Algorithms for Knapsack Problems", D. Pisinger. Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).

Комбинаторна оптимизација
Problem ranca je problem koji je najviše istraživan u kombinatornoj optimizaciji , sa mnogo primena u stvarnom životu . Zbog ovoga je ispitano mnogo specijalnih slučajeva i napravljeno je mnogo generalizacija . Zajedničko za sve verzije je n predmeta , a svaki predmet ima pridruženu vrednost pj i težinu wj . Cilj je sakupiti određeni broj predmeta , tako da vrednost ranca bude maksimalna , ali da težina ranca ne pređe zadatu vrednost W. Uglavnom , ovi koeficijenti se skaliraju da bi bili celi brojevi i gotovo uvek se pretpostavlja da su pozitivni . Problem ranca u osnovnoj formi : Direktne generalizacije Jedna od češćih varijanti je da se svaki predmet može birati više puta . Konkretno , kod problema ograničenog ranca za svaki predmet j , i gornju granicu uj ( koja može biti pozitivan ceo broj ili beskonačno ) za broj predmeta j može biti izabrano : Neograničeni problem ranca ( koji se nekada naziva i celobrojni problem ranca ) ne postavlja gornju granicu za broj predmeta koji mogu da se odaberu : Lueker je pokazao godine da je varijata bez granice NP-kompletan problem . Obe varijatne , i sa ograničenjem i bez ograničenja , imaju aproskimativnu šemu polinomijalnog vremena - FPTAS ( u suštini , kao i kodproblemna ranca ) . Ako se predmeti podele na k klasa označene sa , i ako iz svake klase mora da se uzme tačno jedan predmet , dobija se problem ranca sa višetrukim izborom : Ako su za sve predmete vrednost i težina identični , dobijamo problem zbira podskupa ( često je dat odgovarajući problem , problem odlučivanja ) : Ako imamo n predmeta i m rančeva sa kapacitetima , dobijamo višestruki problem ranca : Kao specijalan slučaj višetrukog problema ranca , kada su vrednosti jednake težinama i svi binovi imaju isti kapacitet , možemo imati i problem zbira višetrukog podskupa : Kvadratni problem ranca : Problem ranca - Unija skupa : SUKP ( Set-Union Knapsack Problem ) je definisao Kellerer i dr . : Dat je skup od predmeta i skup od , tako reći , elemenata , gde svaki predmet odgovara podskupu skupa elemenata \ . Predmeti imaju nenegativne vrednosti , , a elementi nenegativne težine , \ . Konačna težina skupa predemeta je data konačnom težinom elemenata unije odgovarajućih skupa elemenata . Cilj je naći podskup predmeta sa konačnom težinom koja ne prelazi kapacitet ranca i maksimalnu vrednost . Višestruko ograničenje Ako postoji više od jednog ograničenja ( na primer , i granica za obim i granica za težinu , gde obim i težina svakog predmeta nisu povezani ) , dobijamo problem ranca sa višestrukim ograničenjem , višedimenzionalni problem ranca , ili m-dimenzionalni problem ranca . ( Napomena , " dimenzija " se ovde ne odnosi na oblik predmeta . ) Ovo ima ograničenu , i neograničenu varijantu ; neograničena je prikazana ispod . Pokazano je da je varijanta( za sve fiksne ) NP-komplentna oko godine i da nema FPTAS osim ako je P=NP . Ograničena i neograničena varijanta ( za sve fiksne ) imaju istu složenost . Za bilo koje fiksno , ovi problemi imaju pseudo-polinomijalni algoritam ( sličan onom za klasičn problem ranca ) i PTAS . Ranac-slični problemi Ako su sve vrednosti jednake možemo da pokušamo da minimizujemo broj predmeta koji tačno popunjuju ranac : Ako imamo broj skladišta ( iste veličine ) , i želimo da spakujemo svih n predmeta u što je manje moguće skladišta , dobijamo bin-problem ranca , koji je urađen tako da ima indikator za varijable skladište i se trenutno koristi : Problem seckanja zaliha je identičan bin-problemu ranca , ali pošto parcijalne istance obično imaju mnogo manje tipova predmeta , često se koristi druga formulacija . Predmet j je potreban Bj puta , svaki primer premdeta koji može da stane u samo jedan ranac ima promenljivu , xi ( postoji m primera ) , i primer i koristi predmet j bij puta : Ako na višestruki problem ranca , dodamo ograničenje da je svaki podskup veličine n i uklonimo ograničenje za konačnu težinu , dobijamo problem zadatka , koji je takođe problem pronalaženja maksimalnog bipartitivnog poklapanja : U varijanti ranac maksimalne gustine postoji inicijalna težina , i mi uvećavamo gustinu izabranog predemta koi ne ugrožava kapacitet ograničenja : Iako su manje poznadi od problema pomenutih iznad , postoji još nekoliko ranac-sličnih problema , uključujući : Ugneždeni problem ranca Kolapsirajući problem ranca Nelinearan problem ranca Obrnuto-parametarski problem ranca Od ovih , poslednja tri su obrađena u referencnom radu Kellerer-a i drugih , Knapsack Problems . Reference Literatura " Algorithms for Knapsack Problems " , D . Pisinger . Ph .D. thesis , DIKU , University of Copenhagen , Report1 Комбинаторна оптимизација