Motxilaren problema

Wikipedia, Entziklopedia askea
Jump to navigation Jump to search
Motxilaren problemarako adibidea: kutxatxo horien artetik zeintzuk sartuko ditugu motxilan, jakinda sartutako objektuen pisu totala 15kg-ra murriztuta dagoela, beti ere helburua motxilan sartutako objektuen balio totala maximizatzea izanik? Posible da pisua ez izatea problemak duen murrizketa bakarra, bolumena ere murriztuta egotea, adibidez.

Motxilaren problema optimizazio-problema konbinatoriala da. Pisu eta balio ezaguneko objektuen multzo batean balio total maximoko azpimultzoa aurkitzean datza problema, azpimultzoko objektuen pisu totala muga batetik behera egotera murriztuta dagoen kasuan. Tamaina mugatuko motxila batean objektuak sartu behar diren kasuari erreferentzia eginez ematen zaio problemari halako izena; motxilan sartutako objektuen balioen baturak maximoa izan behar du. 

Aplikazio asko ditu, hala nola biomedikuntzan, gaixoari eman beharreko botikak aukeratzeko orduan, antibiotiko karga mugatua denean. Igogailuen diseinuan ere maiz planteatzen da, pisu jakin baterako zenbat pertsona eta nolakoak sar daitezkeen erabakitzeko.