Problem ranca — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
. |
||
Ред 50:
| first = G.S.
| last = Lueker
|
| year = 1975}}</ref> da je varijata bez granice [[НП комплетан проблем|NP-kompletan problem]]. Obe varijatne, i sa ograničenjem i bez ograničenja, imaju aproskimativnu šemu polinomijalnog vremena - [[Polynomial-time approximation scheme|FPTAS]] (u suštini, kao i kod 0-1 problemna ranca).
Линија 128 ⟶ 127:
SUKP (Set-Union Knapsack Problem) je definisao Kellerer i dr.<ref name = KP-KPP>{{Cite book
| author= Kellerer, Hans
| year = 2004
| title = Knapsack Problems
| publisher = [[Springer Verlag]]|id=ISBN 3-540-40286-1
}}</ref> (na 423. str.):
<blockquote>
Линија 154 ⟶ 152:
|}
Pokazano je da je varijanta 0-1 (za sve fiksne <math>m \ge 2</math>) [[НП комплетан проблем|NP-komplentna]] oko 1980. godine i da nema FPTAS osim ako je P=NP.<ref>{{cite news|
Ograničena i neograničena varijanta (za sve fiksne <math>m \ge 2</math>) imaju istu složenost.<ref>{{cite journal|doi = 10.1287/moor.9.2.244|last1 = Magazine|title = A Note on Approximation Schemes for Multidimensional Knapsack Problems|first1 = M. J.|last2 = Chern|first2 = M.-S.
|
| journal = Mathematics of Operations Research
| volume = 9
Линија 266 ⟶ 264:
== Literatura ==
* [http://www.diku.dk/users/pisinger/95-1.pdf "Algorithms for Knapsack Problems"], D. Pisinger. Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).
| |||