Lankide:Aperez512/Proba orria

Bizkar-zorroaren buruketaren adibidea: kutxatxo horien artetik zeintzuk sartuko ditugu bizkar-zorroan, jakinda sartutako gauzakien pisua guztira 15kg-ra murriztuta dagoela, betiere helburua bizkar-zorroan sartutako gauzakien balioa guztira maximizatzea izanik? Litekeena da pisua ez izatea buruketak duen murrizketa bakarra, bolumena ere murriztuta egotea, adibidez.

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.

Historia

Lehenengo aldiz landu zen problema.

Sagu baten irudia:

sagu bat harrapatuta

Irakasle batzuk:

goñi, philip, jon y demás.

macarrones.

Ingenieritza Informatikoa:

Definizioa

Hemen, "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 x₁, x₂, ..., x_n aldagaien sekuentziatik dator non x_i zenbat kopia sartuko diren motxilan adierazten duen.