Kuprinės (knapsack) uždaviniai

Kuprinės uždavinys (knapsack problem) "Kuprinės (knapsack)" uždavinys (dar kitaip vadinamas "vagies" uždaviniu) formuluojamas sekančiai: reikia maksimizuoti bendrą imamų objektų vertę, esant ribotam svoriui. Jo sprendimui čia naudojami apytiksliai algoritmai vadinami MonteKarlo (Monte Carlo), randomizuotos heuristikos (randomized heuristics) ir "godžios" heuristikos (greedy heuristics) vardais. INPUT OUTPUT Įvadas į Kuprinės uždavinių klasę Šie uždaviniai atspindi labai daug šiuolaikinių realių uždavinių. Yra nemažai šio uždavinio modifikacijų ir variacijų. Pateiksime keletą iš jų, dažniausiai sutinkamų. Kuprinės (knapsack) uždavinys (0-1 uždavinys, binarinis kuprinės uždavinys, atskiras atvejis APRIBOTO KUPRINĖS UŽDAVINIO) Apibrėžimas: Duoti objektai su žinomomis vertėmis ir apimtimis (tūriais, svoriais). Rasti rinkinį objektų, kurių vertė būtų didžiausia ir kurie tilptų į duoto fiksuoto dydžio kuprinę. Formalus apibrėžimas: Turime kuprinę duotos talpos c > 0 ir N objektų. Kiekvieno iš jų vertė yra vi > 0 ir svoris (tūris) yra wi > 0. Rasti aibę pasirinktų objektų (δi = 1 jei pasirinktas, 0 jei ne), kurie telpa į kuprinę, ∑i=1N δiwi ≤ c, ir bendra objektų vertė ∑i=1N δivi būtų maksimizuojama. (NP-complete uždavinys) Neapribotas kuprinės uždavinys (unbounded knapsack problem - UKP) Apibrėžimas: Duoti objektų tipai su žinomomis vertėmis ir apimtimis (tūriais, svoriais). Rasti rinkinį objektų, kurių vertė būtų didžiausia ir kurie tilptų į duoto fiksuoto dydžio kuprinę. Kiekvieno tipo objektų skaičius, kurį galima paimti, yra neribojamas. Formalus apibrėžimas: Turime kuprinę duotos talpos c > 0 ir N objektų tipų. Kiekvieno tipo t objekto vertė yra vt > 0 ir svoris (tūris) yra wt > 0. Rasti skaičių nt > 0 kiekvieno tipo objektų, tokį, kad visi jie tilptų į kuprinę, ∑t=1N ntwt ≤ c, ir bendra objektų vertė ∑t=1N ntvt būtų maksimizuojama. Pastaba: svoriai gali būti nebūtinai sveikieji, jie netgi gali būti neigiami. (NP-hard kombinatorinis optimizavimo uždavinys) Apribotas kuprinės uždavinys (bounded knapsack problem) Identiškas neapribotam kuprinės uždaviniui, tik dar egzistuoja ribos (mažiausia ir/arba didžiausia), kiek kiekvienos rūšies objektų reikia paimti: Lt

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!