Valčių krova (2014)
Taškai: 12
Žvejai Simas ir Rimas savo valtis pavadino „Lisa 1“ ir „Lisa 2“. Simas ir Rimas – dvyniai, jie yra vienodo svorio ir gana sunkūs. Kiekviena valtis gali pervežti tik 300 kilogramų prekių, neskaitant vieno iš lydinčių brolių svorio.
Simas ir Rimas gavo užsakymą pervežti uždaras statines, pilnas geriamojo vandens. Broliai nori pakrauti kuo daugiau statinių į valtis, jiems mokama už pergabentus kilogramus.
Sukelkite statines ant valčių taip, kad kiekviena jų būtų maksimaliai pakrauta. Skaičius ant statinės nurodo, kiek ji sveria (kilogramais).
Daugelyje gyvenimo sričių žmonėms reikia optimizuoti įvairius dalykus, dažniausiai siekiant padidinti pelnus ir pan. Optimizavimui dažniausiai naudojami kompiuterių algoritmai, pvz., rasti trumpiausius maršrutus, nustatyti optimalius krovinius ir t. t. Kai kuriuose optimizavimo uždaviniuose gali būti naudojamas godusis algoritmas, kai kiekviename žingsnyje imamas pelningiausias (didžiausias) komponentas. Bet daugelyje situacijų godumo principas nesuteikia optimaliausio sprendimo. Turi būti naudojami sudėtingesni algoritmai. Kaip bebūtų gaila, daugeliui optimizavimo užduočių yra labai sunku rasti optimaliausią sprendimą net ir pasitelkus kompiuterius. Dėl šios priežasties informatikai sukūrė algoritmus, kurie padeda rasti beveik optimalius sprendimus.
Daugiausia į valtis galima pakrauti 590 kilogramų: 120+90+90=300 kg į vieną valtį ir 130+100+60=290 kg į kitą.
Nebūkite godūs, nes jei bandysite pirmiausia pakrauti pačią sunkiausią statinę, tai pergabensite tik 530 kg, t. y. 220+60=280 kg viena ir 130+120=250 kg kita valtimi.