Википедија

Problem ranca — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
м Робот: додато {{subst:User:Autobot/sandbox2}}
м Разне исправке; козметичке измене
Ред 1:
{{loš seminarski}}
'''Problem ranca''' je problem koji je najviše istraživan u [http://en.wikipedia.org/wiki/Combinatorial_optimization[Combinatorial optimization|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 <math>1 \leq j \leq n</math> ima pridruženu vrednost ''p<sub>j</sub>'' i težinu ''w<sub>j</sub>''. Cilj je sakupiti određeni broj predmeta, tako da vrednost ranca bude maksimalna, ali da ne pređe zadatu vrednost ''W''. Uglavnom, ovi koeficijenti se skaliraju da bi bili celi brojevi i gotovo uvek se pretpostavlja da su pozitivni.
Ред 52:
| contribution = Two NP-complete problems in nonnegative integer programming
| title = Report No. 178, Computer Science Laboratory, Princeton
| 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 - [http://en.wikipedia.org/wiki/[Polynomial-time_approximation_schemetime approximation scheme|FPTAS]] (u suštini, kao i kod 0-1 problemna ranca).
 
Ako se predmeti podele na ''k'' klasa označene sa <math>N_i</math>, i ako iz svake klase mora da se uzme tačno jedan predmet, dobija se '''problem ranca sa višetrukim izborom''':
Ред 163:
| pages=244-247|year = 1984}}</ref>
 
Za bilo koje fiksno <math>m \ge 2</math>, ovi problemi imaju [http://en.wikipedia.org/wiki/[Pseudo-polynomial_timepolynomial time|pseudo-polinomijalni]] algoritam (sličan onom za klasičn problem ranca) i [http://en.wikipedia.org/wiki/[Polynomial-time_approximation_schemetime approximation scheme|PTAS]].<ref name = KP-KPP />
 
== Ranac-slični problemi ==
Ред 181:
|}
 
Ako imamo broj skladišta (iste veličine), i želimo da spakujemo svih ''n'' predmeta u što je manje moguće skladišta, dobijamo [http://en.wikipedia.org/wiki/Bin_packing_problem[Bin packing problem|bin-problem ranca]], koji je urađen tako da ima indikator za varijable <math>y_i=1 \Leftrightarrow</math> skladište ''i'' se trenutno koristi:
 
{|
Ред 203:
|<math>\forall i \in \{1,\ldots,n\} \wedge \forall j \in \{1,\ldots,n\}</math>
|}
* [http://en.wikipedia.org/wiki/Cutting_stock_problem[Cutting stock problem|Problem seckanja zaliha]] je identičan [http://en.wikipedia.org/wiki/Bin_packing_problem[Bin packing problem|bin-problemu ranca]], ali pošto parcijalne istance obično imaju mnogo manje tipova predmeta, često se koristi druga formulacija. Predmet ''j'' je potreban ''B<sub>j</sub>'' puta, svaki primer premdeta koji može da stane u samo jedan ranac ima promenljivu, ''x<sub>i</sub>'' (postoji ''m'' primera), i primer ''i'' koristi predmet ''j'' ''b<sub>ij</sub>'' puta:
 
{|
Ред 218:
|}
 
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 '''[http://en.wikipedia.org/wiki/Assignment_problem[Assignment problem|problem zadatka]]''', koji je takođe problem pronalaženja maksimalnog '''[http://en.wikipedia.org/wiki/Bipartite_matching[Bipartite matching#Maximum_bipartite_matchingsMaximum bipartite matchings|bipartitivnog poklapanja]]''':
 
{|
Преузето из „https://sr.wikipedia.org/wiki/Problem_ranca”