2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2018

 

Liftas

Taškai: 9

Bebrų grupė lankosi gražioje vietovėje ir nori pakilti liftu į bokšto apžvalgos aikštelę. Jau vėlu, ir liftas pakils į aikštelę tik dukart, be to, kelti vienu metu jis gali ne daugiau nei 30 kg.

Kaip paskirstyti bebrus į lifto kėlimus taip, kad į aikštelę pakiltų kuo daugiau bebrų? Nutempkite bebrus į liftus apačioje.

Paaiškinimas

Šiam uždaviniui tinka labai daug paskirstymo variantų, oišnagrinėti juos visus užtruktų labai ilgai. Tokiu atveju, turime rasti kuo geresnį sprendinį, kuris ne visada optimalus.

Informatikoje neretai kalbama apie praktiškai neišsprendžiamus uždavinius. Bet šiuo atveju, vadovavomės praktiška strategija: sulaipinom kuo daugiau bebrų į pirmą liftą ir bandėm apkeisti po vieną. Toks sprendimo būdas, kurį pasitelkus randamas geras, bet ne būtinai geriausias sprendinys, vadinamas euristika.

Raktiniai žodžiai: optimizavimas, kuprinės uždavinys, euristinis sprendimo būdas.

Atsakymas

Galima bandyti į vieną liftą sulaipinti kuo daugiau bebrų, pradedant nuo lengviausio: 2 + 3 + 5 + 8 + 9 = 27 kg, o į antrą liftą 9 + 12 = 21 kg (8 bebrai), bet įmanoma sulaipinti į liftus ir 9 bebrus (pakeitus 9 kg bebrą 12 kg bebru pirmame kėlime, į antrą kėlimą tilps likęs 9 kg bebras, ir abiem kėlimais bus keliama po 30 kg):

Yra ir daugiau galimų sprendimo būdų.

Interaktyvi užduotis