4. Suveníry balíme

Táto úloha je teoretická. Ako svoje riešenie odovzdaj PDF súbor, v ktorom bude tvoje riešenie aj so zdôvodnením, prečo je správne. Po konci kola ti riešenie opraví vedúci, a napíše ti komentár – povie ti kde si spravil/a chyby, prípadne ti poradí ako vieš svoje riešenia zlepšiť.

Ak máš hocijaké otázky k tejto úlohe, napíš Alici ([email protected]) alebo Štepimu ([email protected]).

Domorodci boli Miške veľmi vďační za pomoc s delením jedla, rozhodli sa jej preto venovať kopu suvenírov. Miška ale zistila, že na ne budú potrebovať nový batoh.

Suveníry, ktoré si chce zobrať, zaberajú isté množstvo priestoru a každý z batohov má taktiež svoj maximálny objem vecí, ktoré sa doň zmestia. Najlepšia možná batožina je taká, ktorá odnesie všetky suveníry od domorodcov a zároveň v nej zostane čo najmenej nevyužitého priestoru. Miška so Štepim majú na výber niekoľko batohov v rade. Ich presné veľkosti nevedia, ale vedia, že sú zoradené od najmenšieho po najväčší.

Pri hľadaní vhodného batohu vedia v jednom kroku naplniť vecami jeden batoh. Ak sa tam všetky veci nezmestia, tak im ostane ten zvyšok. Takto teda zistia, že im niečo zostalo, ale nevedia, koľko toho presne je. Zvyšok suvenírov ďalej môžu skúsiť dať do iných batohov bez toho, aby vyberali veci z plného batohu.

Príklad

Predstavme si, že by Štepi a Miška mali dva batohy s veľkosťami \(3\) a \(10\) a k tomu \(8\) vecí (vecí, ktoré dokopy zaberajú \(8\) jednotiek priestoru). Potom ich môžu skúsiť dať do menšieho batohu, ale tam sa všetky nezmestia, ostane im \(5\) vecí. Tak môžu týchto \(5\) vecí skúsiť dať do väčšieho batohu, kde by sa už zmestili. Potom môžu napríklad vyprázdniť menší batoh a odložiť si tie veci na nejakú kôpku, a ďalej vybrať tých \(5\) vecí z väčšieho batohu a skúsiť nimi naplniť ten menší. V menšom batohu teda budú \(3\) veci a vo väčšom ostanú \(2\).

Miška a Štepi ale tieto čísla nepoznajú, takže vedia len, že po tom, čo urobia tieto kroky, majú kôpku takej veľkosti, ako je ten menší batoh, potom ešte raz plný menší batoh a ešte nejaké veci vo väčšom batohu, menej ako je jeho kapacita, ale nevedia koľko presne.

Tento príklad nesúvisí s riešením úlohy, je tu len na to, aby ste si vedeli lepšie predstaviť, čo sa dá s batohmi a vecami robiť.

Úlohy

1. (30 bodov) Ak majú Štepi s Miškou vybrať jeden batoh pre všetky suveníry, ako vedia vybrať taký, ktorý bude najlepšie spĺňať podmienky? Mohli by zaradom prejsť všetky batohy, ale to by trvalo príliš dlho. Chcú si užiť čo najviac času v pralesoch s domorodcami, preto by mali použiť čo najmenej krokov.

2. (70 bodov) Po dlhej výprave ich však už bolia chrbty a výhodnejšie by bolo rozdeliť suveníry medzi Miškou a Štepim do dvoch batohov. Suveníry aj objem, ktorý zaberajú, sa môžu akokoľvek rozdeliť na dve časti. V tejto podúlohe môžete navyše predpokladať, že žiadny batoh nie je väčší ako všetky suveníry dokopy.

   Ak majú vybrať dva batohy pre dve kôpky suvenírov, ako vedia vybrať tú najlepšiu dvojicu? Tiež nechcú skúšať každú dvojicu batohov osobitne.