b"\n_START_ARTICLE_\nProblema rucsacului\n_START_PARAGRAPH_\nProblema rucsacului\xc2\xa0este o problem\xc4\x83 de\xc2\xa0optimizare combinatoric\xc4\x83: Dat\xc4\x83 fiind o mul\xc8\x9bime de elemente, fiecare cu o greutate \xc8\x99i o valoare, se determin\xc4\x83 num\xc4\x83rul din fiecare element al mul\xc8\x9bimii care poate fi inclus \xc3\xaentr-o colec\xc8\x9bie, astfel \xc3\xaenc\xc3\xa2t greutatea total\xc4\x83 s\xc4\x83 fie mai mic\xc4\x83 sau egal\xc4\x83 cu o anumit\xc4\x83 limit\xc4\x83 \xc8\x99i valoarea total\xc4\x83 s\xc4\x83 fie c\xc3\xa2t mai mare. Ea \xc3\xae\xc8\x99i trage numele de la problema cu care se confrunt\xc4\x83 cineva care este obligat s\xc4\x83 umple un\xc2\xa0rucsac\xc2\xa0de dimensiune fix\xc4\x83\xc2\xa0cu elementele cele mai valoroase._NEWLINE_Problema apare adesea \xc3\xaen alocarea resurselor unde exist\xc4\x83 constr\xc3\xa2ngeri financiare \xc8\x99i este studiat\xc4\x83 \xc3\xaen domenii cum ar fi combinatorica, informatica, teoria complexit\xc4\x83\xc8\x9bii, criptografia, matematicile aplicate\xc2\xa0\xc8\x99i\xc2\xa0jocurile cu echipe sportive imaginare._NEWLINE_Problema rucsacului a fost studiat\xc4\x83 de peste un secol, primele lucr\xc4\x83ri dat\xc3\xa2nd de la 1897.\xc2\xa0Denumirea\xc2\xa0\xe2\x80\x9eproblema rucsacului\xe2\x80\x9d dateaz\xc4\x83 de la \xc3\xaenceputul activit\xc4\x83\xc8\x9bii matematicianului\xc2\xa0Tobias Dantzig (1884\xe2\x80\x931956), \xc8\x99i se refer\xc4\x83 la problema banal\xc4\x83 de \xc3\xaempachetare a celor mai valoroase sau utile elemente f\xc4\x83r\xc4\x83 a supra\xc3\xaenc\xc4\x83rca bagajul.\n_START_SECTION_\nAplica\xc8\x9bii\n_START_PARAGRAPH_\nUn studiu efectuat \xc3\xaen 1998 la Stony Brook University Algorithm Repository\xc2\xa0a ar\xc4\x83tat c\xc4\x83, din 75 de probleme de algoritmic\xc4\x83, problema rucsacului fost a 18-a cea mai popular\xc4\x83 \xc8\x99i a 4-a cea mai necesar\xc4\x83 dup\xc4\x83 arborii kd, arborii de sufixe, \xc8\x99i problema bin packing._NEWLINE_Probleme ale rucsacului apar \xc3\xaen lumea real\xc4\x83 \xc3\xaen procesele de luare a deciziilor \xc3\xaentr-o varietate de domenii, cum ar fi g\xc4\x83sirea unei metode de a t\xc4\x83ia materia prim\xc4\x83 cu risip\xc4\x83 minim\xc4\x83, selec\xc8\x9bia de investi\xc8\x9bii \xc8\x99i portofolii, selec\xc8\x9bia de active titrizarea garantat\xc4\x83 cu active, \xc8\x99i generarea de chei pentru Merkle\xe2\x80\x93Hellman \xc8\x99i alte criptosisteme bazate pe problema rucsacului._NEWLINE_O aplica\xc8\x9bie timpurie a problemei rucsacului a fost \xc3\xaen construc\xc8\x9bia \xc8\x99i notarea testelor \xc3\xaen care cei care dau testul au de ales la care \xc3\xaentreb\xc4\x83ri s\xc4\x83 r\xc4\x83spund\xc4\x83. Pentru exemple mici, procesul este destul de simplu. De exemplu, dac\xc4\x83 un examen con\xc8\x9bine 12 \xc3\xaentreb\xc4\x83ri, fiecare \xc3\xaen valoare de 10 puncte, examina\xc8\x9bii au nevoie s\xc4\x83 r\xc4\x83spund\xc4\x83 la doar 10 \xc3\xaentreb\xc4\x83ri pentru a ob\xc8\x9bine punctajul maxim de 100 de puncte. Cu toate acestea, pe teste cu o distribu\xc8\x9bie eterogen\xc4\x83 a valorilor \xc3\xaentreb\xc4\x83rilor\xe2\x80\x94de exemplu, diferite \xc3\xaentreb\xc4\x83ri au punctaje diferite\xe2\x80\x94 este mult mai dificil s\xc4\x83 se fac\xc4\x83 o alegere. Feuerman \xc8\x99i Weiss au propus un sistem \xc3\xaen care elevii primesc un test eterogen cu un total de 125 de puncte posibile. Elevii sunt ruga\xc8\x9bi s\xc4\x83 r\xc4\x83spund\xc4\x83 la toate \xc3\xaentreb\xc4\x83rile dup\xc4\x83 cum pot ei mai bine. Dintre posibilele submul\xc8\x9bimi de \xc3\xaentreb\xc4\x83ri al c\xc4\x83ror punctaj total ajunge la 100, un algoritm de problema rucsacului ar determina care submul\xc8\x9bime ofer\xc4\x83 fiec\xc4\x83rui elev cel mai mare scor posibil.\n_START_SECTION_\nRezolvarea\n_START_PARAGRAPH_\nSunt disponibili mai mul\xc8\x9bi algoritmi\xc2\xa0pentru rezolvarea problemei rucsacului, baza\xc8\x9bi pe abordarea cu programare dinamic\xc4\x83, branch and bound sau cu\xc2\xa0hibridiz\xc4\x83ri\xc2\xa0de ambele abord\xc4\x83ri.\n_START_SECTION_\nMeet-in-the-middle\n_START_PARAGRAPH_\nUn alt algoritm pentru problema 0/1 a rucsacului, descoperit \xc3\xaen 1974  \xc8\x99i uneori numit \xe2\x80\x9emeet-in-the-middle\xe2\x80\x9d din cauza paralelor cu un algoritm cu nume similar din criptografie, este exponen\xc8\x9bial\xc4\x83 \xc3\xaen num\xc4\x83rul de elemente diferite, dar poate fi de preferat fa\xc8\x9b\xc4\x83 de algoritmul PD atunci c\xc3\xa2nd W este mare \xc3\xaen compara\xc8\x9bie cu n. \xc3\x8en special, dac\xc4\x83  sunt nenegative, dar nu \xc3\xaentregi, algoritmul de programare dinamic\xc4\x83 ar putea fi utilizat \xc3\xaen continuare prin scalare \xc8\x99i rotunjire (de exemplu, folosind\xc2\xa0aritmetica \xc3\xaen virgul\xc4\x83 fix\xc4\x83), dar dac\xc4\x83 problema necesit\xc4\x83 d\xc2\xa0cifre frac\xc8\x9bionare de precizie pentru a ajunge la r\xc4\x83spunsul corect, W va trebui s\xc4\x83 fie scalat cu un factor de\xc2\xa0 \xc8\x99i algoritmul PD va avea nevoie de un spa\xc8\x9biu de\xc2\xa0\xc2\xa0\xc8\x99i de un timp de\xc2\xa0._NEWLINE__NEWLINE_  intrare:_NEWLINE_    o mul\xc8\x9bime de obiecte cu greut\xc4\x83\xc8\x9bi \xc8\x99i valori_NEWLINE_  ie\xc8\x99ire:_NEWLINE_cea mai mare valoare total\xc4\x83 a unei submul\xc8\x9bimi_NEWLINE_\xc3\xaemparte {1...n} \xc3\xaen dou\xc4\x83 mul\xc8\x9bimi A \xc8\x99i B, de dimensiuni aproximativ egale_NEWLINE__NEWLINE_ calculeaz\xc4\x83 ponderile \xc8\x99i valorile tuturor submul\xc8\x9bimilor din fiecare mul\xc8\x9bime_NEWLINE_ pentru fiecare submul\xc8\x9bime a lui A_NEWLINE_    se g\xc4\x83se\xc8\x99te o submul\xc8\x9bime a lui B cu cea mai mare valoare, astfel \xc3\xaenc\xc3\xa2t greutatea total\xc4\x83 s\xc4\x83 fie mai mic\xc4\x83 dec\xc3\xa2t W_NEWLINE_ se \xc8\x9bine eviden\xc8\x9ba celei mai mari valori combinate g\xc4\x83site_NEWLINE_Algoritmul ocup\xc4\x83 un spa\xc8\x9biu de , \xc8\x99i implement\xc4\x83rile eficiente ale pasului 3 (de exemplu, sortarea submul\xc8\x9bimilor lui B dup\xc4\x83 greutate, elimin\xc3\xa2nd submul\xc8\x9bimile din B care c\xc3\xa2nt\xc4\x83resc mai mult dec\xc3\xa2t alte submul\xc8\x9bimi din B de valoare mai mare sau egal\xc4\x83, \xc8\x99i folosind c\xc4\x83utarea binar\xc4\x83 pentru a g\xc4\x83si cea mai bun\xc4\x83 combina\xc8\x9bie) duc la un timp de execu\xc8\x9bie de . Ca \xc8\x99i \xc3\xaen cazul\xc2\xa0atacurilor meet-in-the-middle\xc2\xa0din criptografie, acesta \xc3\xaembun\xc4\x83t\xc4\x83\xc8\x9be\xc8\x99te timpul de\xc2\xa0\xc2\xa0al unui algoritm naiv de for\xc8\x9b\xc4\x83 brut\xc4\x83 (examinarea tuturor submul\xc8\x9bimilor lui {1...n}), cu pre\xc8\x9bul utiliz\xc4\x83rii de spa\xc8\x9biu exponen\xc8\x9bial, \xc3\xaen loc de constant.\n_START_SECTION_\nAlgoritmi de aproximare\n_START_PARAGRAPH_\nCa \xc8\x99i pentru majoritatea problemelor NP-complete, s-ar putea s\xc4\x83 fie suficient s\xc4\x83 se g\xc4\x83seasc\xc4\x83 solu\xc8\x9bii viabile, chiar dac\xc4\x83 acestea nu sunt optime. De preferin\xc8\x9b\xc4\x83, \xc3\xaens\xc4\x83, aproximarea vine cu o garan\xc8\x9bie cu privire la diferen\xc8\x9ba dintre valoarea solu\xc8\x9biei g\xc4\x83sit\xc4\x83 \xc8\x99i valoarea solu\xc8\x9biei optime._NEWLINE_Ca \xc8\x99i \xc3\xaen mul\xc8\x9bi algoritmi utili dar complec\xc8\x99i computa\xc8\x9bional, s-au f\xc4\x83cut cercet\xc4\x83ri substan\xc8\x9biale privind crearea \xc8\x99i analiza algoritmilor care aproximeaz\xc4\x83 o solu\xc8\x9bie. Problema rucsacului, de\xc8\x99i NP-hard, este una dintr-o colec\xc8\x9bie de algoritmi care \xc3\xaenc\xc4\x83 pot fi aproxima\xc8\x9bi p\xc3\xa2n\xc4\x83 la orice grad specificat. Aceasta \xc3\xaenseamn\xc4\x83 c\xc4\x83 problema are o schem\xc4\x83 de aproximare \xc3\xaen timp polinomial. Mai exact, problema rucsacului are o schem\xc4\x83 de aproximare \xc3\xaen timp polinomial complet (FPTAS).\n_START_SECTION_\nAlgoritm de aproximare greedy\n_START_PARAGRAPH_\nGeorge Dantzig a propus un algoritm greedy de aproximare\xc2\xa0pentru a rezolva problema rucsacului nem\xc4\x83rginit\xc4\x83.\xc2\xa0Versiunea lui sorteaz\xc4\x83 elementele \xc3\xaen ordinea descresc\xc4\x83toare a valorii pe unitatea de greutate, . Se trece apoi la introducerea \xc3\xaen sac, \xc3\xaencep\xc3\xa2nd cu un num\xc4\x83r c\xc3\xa2t mai mare de exemplare din primul tip de element p\xc3\xa2n\xc4\x83 c\xc3\xa2nd nu mai este spa\xc8\x9biu \xc3\xaen rucsac pentru mai multe. Dat fiind c\xc4\x83 exist\xc4\x83 num\xc4\x83r nelimitat din fiecare tip de element, dac\xc4\x83 este valoarea maxim\xc4\x83 de elemente care se \xc3\xaencadreaz\xc4\x83 \xc3\xaen sac, atunci algoritmul greedy este garantat s\xc4\x83 ob\xc8\x9bin\xc4\x83 cel pu\xc8\x9bin o valoare de . Cu toate acestea, pentru problema m\xc4\x83rginit\xc4\x83, unde rezerva din fiecare tip de element este limitat\xc4\x83, algoritmul poate fi departe de optim.\n_START_SECTION_\nSchema de aproximare \xc3\xaen timp polinomial complet\n_START_PARAGRAPH_\nSchema de aproximare \xc3\xaen timp polinomial complet\xc2\xa0(FPTAS) pentru problema rucsacului profit\xc4\x83 de faptul c\xc4\x83 motivul pentru care problema nu are solu\xc8\x9bii \xc3\xaen timp polinomial este c\xc4\x83 profiturile asociate cu elementele nu sunt restric\xc8\x9bionate. Dac\xc4\x83 se rotunjesc unele din cele mai pu\xc8\x9bin semnificative cifre ale valorilor de profit, atunci ele vor fi m\xc4\x83rginite de un polinom \xc8\x99i 1/\xce\xb5 unde \xce\xb5 este o limit\xc4\x83 a corectitudinii solu\xc8\x9biei. Aceast\xc4\x83 restric\xc8\x9bie \xc3\xaenseamn\xc4\x83 c\xc4\x83 un algoritm poate g\xc4\x83si \xc3\xaen timp polinomial o solu\xc8\x9bie corect\xc4\x83 \xc3\xaentr-un factor de (1-\xce\xb5) de solu\xc8\x9bia optim\xc4\x83._NEWLINE__NEWLINE_ intrare: _NEWLINE_   \xce\xb5 \xe2\x88\x88 (0,1]_NEWLINE_   o list\xc4\x83 de n elemente, specificat\xc4\x83 prin valorile lor,  \xc8\x99i greut\xc4\x83\xc8\x9bile_NEWLINE_ ie\xc8\x99ire:_NEWLINE_   S', solu\xc8\x9bia FPTAS_NEWLINE__NEWLINE_ P := max  // cea mai mare valoare_NEWLINE_ K := \xce\xb5 _NEWLINE_ for i from 1 to n do_NEWLINE_      := _NEWLINE_ end for_NEWLINE_ return solu\xc8\x9bia, S', folosind valorile  din programul dinamic prezentat mai sus_NEWLINE_Teorem\xc4\x83: mul\xc8\x9bimea\xc2\xa0 calculat\xc4\x83 prin algoritmul de mai sus \xc3\xaendepline\xc8\x99te , unde\xc2\xa0 este o solu\xc8\x9bie optim\xc4\x83.\n_START_SECTION_\nVaria\xc8\x9bii\n_START_PARAGRAPH_\nExist\xc4\x83 mai multe varia\xc8\x9bii ale problemei rucsacului, ap\xc4\x83rute din num\xc4\x83rul mare de aplica\xc8\x9bii ale problemei de baz\xc4\x83. Principalele varia\xc8\x9bii apar prin schimbarea num\xc4\x83rului unui parametru al problemei, cum ar fi num\xc4\x83rul de elemente, num\xc4\x83rul de obiective, sau chiar num\xc4\x83rul de rucsacuri.\n_START_SECTION_\nProblema rucsacului multiobiectiv\n_START_PARAGRAPH_\nAceast\xc4\x83 varia\xc8\x9bie modific\xc4\x83 obiectivul individual al umplerii rucsacului. \xc3\x8en loc de un singur obiectiv, cum ar fi maximizarea profitului monetar, obiectivul ar putea avea mai multe dimensiuni. De exemplu, ar putea fi obiective de mediu, sociale, \xc8\x99i economice. Probleme frecvent abordate includ optimiz\xc4\x83rile portofoliilor \xc8\x99i ale logisticii de transport._NEWLINE_Ca exemplu concret, se presupune gestiunea unui vas de croazier\xc4\x83. Trebuie s\xc4\x83 se decid\xc4\x83 c\xc3\xa2\xc8\x9bi actori de comedie s\xc4\x83 se angajeze. Acest nu poate ocupa mai mult de o ton\xc4\x83 de pasageri \xc8\x99i actorii trebuie s\xc4\x83 c\xc3\xa2nt\xc4\x83reasc\xc4\x83 mai pu\xc8\x9bin de 1000 kg. Fiecare actor are o greutate, aduce o valoare de business \xc3\xaen func\xc8\x9bie de popularitatea sa \xc8\x99i cere un anumit salariu. \xc3\x8en acest exemplu sunt mai multe obiective. Se dore\xc8\x99te, desigur, maximizarea popularit\xc4\x83\xc8\x9bii actorilor \xc8\x99i minimizarea salariului. De asemenea, se dore\xc8\x99te un num\xc4\x83r c\xc3\xa2t mai mare de actori.\n_START_SECTION_\nProblema rucsacului multidimensional\xc4\x83\n_START_PARAGRAPH_\n\xc3\x8en aceast\xc4\x83 variant\xc4\x83, greutatea elementului\xc2\xa0i este dat\xc4\x83 de un vector D-dimensional  \xc8\x99i rucsacul are un vector de capacit\xc4\x83\xc8\x9bi D-dimensional\xc2\xa0. Obiectivul este de a maximiza suma valorilor elementelor \xc3\xaen rucsac, astfel \xc3\xaenc\xc3\xa2t suma greut\xc4\x83\xc8\x9bilor pe fiecare dimensiune\xc2\xa0d s\xc4\x83 nu dep\xc4\x83\xc8\x99easc\xc4\x83 ._NEWLINE_Calculul problemei multi-dimensionale a rucsacului este mai greu dec\xc3\xa2t cel al problemei simple; chiar \xc8\x99i pentru  problema nu are nici m\xc4\x83car\xc2\xa0schem\xc4\x83 de aproximare \xc3\xaen timp polinomial\xc2\xa0dec\xc3\xa2t dac\xc4\x83 PNP.\xc2\xa0Cu toate acestea, algoritmul din Cohen & Grebla 2014 este demonstrat a rezolva eficient cazurile rare. Un exemplu de problem\xc4\x83 multi-dimensional\xc4\x83 a rucsacului este rar\xc4\x83 dac\xc4\x83 exist\xc4\x83 o mul\xc8\x9bime\xc2\xa0 pentru  astfel \xc3\xaenc\xc3\xa2t pentru fiecare element i,  astfel \xc3\xaenc\xc3\xa2t\xc2\xa0 \xc8\x99i . Astfel de situa\xc8\x9bii apar, de exemplu, atunci c\xc3\xa2nd se planific\xc4\x83 pachetele \xc3\xaentr-o re\xc8\x9bea f\xc4\x83r\xc4\x83 fir cu noduri de retransmisie.\xc2\xa0Algoritmul din\xc2\xa0\xc2\xa0rezolv\xc4\x83 \xc8\x99i el cazurile rare ale variantei cu alegere multipl\xc4\x83._NEWLINE_Algoritmul IHS (Increasing Height Shelf) este optim pentru problema rucsacului 2D (acoperirea cu p\xc4\x83trate a unui p\xc4\x83trat unitar bidimensional): atunci c\xc3\xa2nd exist\xc4\x83 cel mult cinci p\xc4\x83trate \xc3\xaentr-o acoperire optim\xc4\x83.\n_START_SECTION_\nProblema rucsacurilor multiple\n_START_PARAGRAPH_\nAceast\xc4\x83 varia\xc8\x9bie este similar\xc4\x83 cu problema bin packing, dar difer\xc4\x83 de aceasta prin aceea c\xc4\x83 se poate alege o submul\xc8\x9bime de elemente, pe c\xc3\xa2nd, \xc3\xaen problema bin packing, toate produsele trebuie s\xc4\x83 fie ambalate \xc3\xaen anumite compartimente. Conceptul este c\xc4\x83 exist\xc4\x83 mai multe rucsacuri. Aceast\xc4\x83 schimbare ar\xc2\xa0p\xc4\x83rea banal\xc4\x83, dar nu este echivalent\xc4\x83 cu ad\xc4\x83ugarea la capacitatea ini\xc8\x9bial\xc4\x83. Aceast\xc4\x83 varia\xc8\x9bie este folosit\xc4\x83 \xc3\xaen multe probleme de \xc3\xaenc\xc4\x83rcare \xc8\x99i planificare din cercetarea opera\xc8\x9bional\xc4\x83 \xc8\x99i are schem\xc4\x83 de aproximare \xc3\xaen timp polinomial.\n_START_SECTION_\nProblema rucsacului p\xc4\x83tratic\xc4\x83\n_START_PARAGRAPH_\nA\xc8\x99a cum este descris\xc4\x83 de c\xc4\x83tre Wu et al.:_NEWLINE_Problema problema p\xc4\x83tratic\xc4\x83\xc2\xa0(QKP) maximizeaz\xc4\x83 o func\xc8\x9bie obiectiv p\xc4\x83tratic\xc4\x83 supus\xc4\x83 unei constr\xc3\xa2ngeri binare \xc8\x99i liniare de capacitate._NEWLINE__NEWLINE_Problema rucsacului p\xc4\x83tratic\xc4\x83 fost discutat\xc4\x83 sub acest titlu de Gallo, Hammer \xc8\x99i Simeone \xc3\xaen 1980. Gallo \xc8\x99i Simeone pun \xc3\xaens\xc4\x83 prima tratare a problemei pe seama lui Witzgall \xc3\xaen 1975.\n_START_SECTION_\nProblema sumei submul\xc8\x9bimilor\n_START_PARAGRAPH_\nProblema sumei submul\xc8\x9bimilor\xc2\xa0este un caz special al problemelor de decizie \xc8\x99i\xc2\xa00-1\xc2\xa0\xc3\xaen care pentru fiecare tip de element, greutatea este egal\xc4\x83 cu valoarea: . \xc3\x8en domeniul criptografiei, termenul problema rucsacului este adesea folosit pentru a se referi \xc3\xaen mod special la problema sumei submul\xc8\x9bimilor \xc8\x99i este cunoscut\xc4\x83 ca fiind una dintre cele 21 de probleme NP-complete ale lui Karp._NEWLINE_Generalizarea problemei sumei submul\xc8\x9bimilor se nume\xc8\x99te problema sumei submul\xc8\x9bimilor multipl\xc4\x83, \xc3\xaen care exist\xc4\x83 mai multe compartimente cu aceea\xc8\x99i capacitate. S-a demonstrat c\xc4\x83 generalizarea nu are schem\xc4\x83 de aproximare \xc3\xaen timp polinomial."