Turinys:
Apibrėžimas - ką reiškia „Knapsack“ problema?
Kuprinės problema yra optimizavimo problema, naudojama iliustruoti problemą ir jos sprendimą. Savo pavadinimą jis kildina iš scenarijaus, kai ribojamas daiktų, kuriuos galima sudėti į fiksuoto dydžio krepšį, skaičius. Atsižvelgiant į daiktų, turinčių tam tikrą svorį ir vertes, rinkinį, siekiama, kad į kuprinę būtų kuo daugiau vertės, atsižvelgiant į kuprinės svorį.
„Techopedia“ paaiškina „Knapsack“ problemą
Kuprinės problema yra kombinuotosios optimizacijos problemos pavyzdys, matematikos ir informatikos tema apie optimalų objektą tarp objektų rinkinio. Tai yra problema, kuri buvo tyrinėjama daugiau nei šimtmetį ir yra dažniausiai naudojama pavyzdinė problema derinant optimizavimą, kai reikia optimalaus objekto arba baigtinio sprendimo, kai neįmanoma išsami paieška. Problemą galima rasti realaus pasaulio scenarijuose, tokiuose kaip išteklių paskirstymas esant finansiniams apribojimams ar net renkantis investicijas ir portfelius. Tai taip pat galima rasti tokiose srityse kaip taikomoji matematika, sudėtingumo teorija, kriptografija, kombinatorika ir informatika. Nesunkiai tai yra pati svarbiausia logistikos problema.
Kalbant apie kuprinės problemą, duoti daiktai turi bent du požymius - daikto vertę, kuri daro įtaką jo svarbai, ir daikto svorį ar tūrį, kuris yra jo apribojimo aspektas. Kadangi išsami paieška neįmanoma, problemas galima suskaidyti į mažesnes subproblemas ir paleisti jas rekursyviai. Tai vadinama optimalia postruktūra. Tai taikoma tik vienai prekei vienu metu, o dabartinis svoris vis dar yra krepšyje. Problemų sprendėjui reikia tik nuspręsti, ar paimti daiktą, ar ne, atsižvelgiant į svorį, kurį vis dar galima priimti. Tačiau jei tai programa, pakartotinis skaičiavimas nėra savarankiškas ir gali sukelti problemų. Čia galima pritaikyti dinaminio programavimo metodus. Kiekvienos papildomos problemos sprendimai saugomi taip, kad skaičiavimas turėtų įvykti tik vieną kartą.
