Lankide:Aperez512/Proba orria
Bizkar-zorroaren buruketa optimizazio-buruketa konbinatoriala da. Pisu eta balio ezaguneko gauzakien multzo batean guztizko gehieneko balioko azpimultzoa aurkitzean datza, azpimultzoko gauzakien guztizko pisua muga batetik behera egotera murriztuta dagoen kasuan. Neurri mugatuko bizkar-zorro batean gauzakiak sartu behar diren kasuari aipamen eginez ematen zaio buruketari halako izena; bizkar-zorroan sartutako gauzakien balioen baturak gehienekoa izan behar du.
Aplikazio asko ditu, hala nola biosendagintzan, gaixoari eman beharreko sendagaiak aukeratzeko orduan, antibiotiko-zama mugatua denean. Igogailuak marraztean ere maiz ezartzen da, pisu jakin baterako zenbat pertsona eta nolakoak sar daitezkeen erabakitzeko.[1]
Historia
aldatuLehenengo aldiz landu zen problema.
Sagu baten irudia:
Irakasle batzuk:
Definizioa
aldatuHemen, "xi" da "i" itemaren instantzia kopurua, knapsackean sartzeko. Informalki, knapsack-eko elementuen balioen batura maximizatzea da arazoa, pisuen batura knapsack-en ahalmena baino txikiagoa edo berdina izan dadin.
Arazoak konsistitzen du bizkar-zorro batean objektuak sartzea, objektuek dituen balioa maximizatzeko baldin eta bizkar-zorroaren pisu (edo bolumen) maximoa ez bada gainditzen. Problemaren soluzioa x1, x2, ..., xn aldagaien sekuentziatik dator non xi zenbat kopia sartuko diren motxilan adierazten duen.
Erreferentziak
aldatu- ↑ (Ingelesez) Ben-Amram, Amir M.; Galil, Zvi. (2001-01). «Topological Lower Bounds on Algebraic Random Access Machines» SIAM Journal on Computing 31 (3): 722–761. doi: . ISSN 0097-5397. (Noiz kontsultatua: 2024-01-26).