Problem ranca — разлика између измена
Садржај обрисан Садржај додат
м Разне исправке |
м ref=harv |
||
Ред 158:
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|authors = Gens, G. V. and Levner, E. V.|year=1979|title=Complexity and Approximation Algorithms for Combinatorial Problems: A Survey|publisher = Central Economic and Mathematical Institute, Academy of Sciences of the USSR, Moscow}}</ref><ref>{{cite journal|author8 = Korte, B. and Schrader, R. | year = 1980 | title = On the Existence of Fast Approximation Schemes| journal = Nonlinear Programming | volume = 4 | publisher = Academic Press | pages = 415–437}}</ref>
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.
Za bilo koje fiksno <math>m \ge 2</math>, ovi problemi imaju [http://en.wikipedia.org/wiki/Pseudo-polynomial_time pseudo-polinomijalni] algoritam (sličan onom za klasičn problem ranca) i [http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme PTAS].<ref name = KP-KPP />
Ред 269:
== Literatura ==
* {{Cite book |ref= harv|author= Kellerer, Hans and Pferschy, Ulrich and Pisinger, David| year = 2004| title = Knapsack Problems| publisher = [[Springer Verlag]]| isbn = 3-540-40286-1| unused_data = Kellerer
* [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).
| |||