Programátorské strategie

Úloha Jak pobrat odměnu

Příběh: Svojí nebojácností a schopnostmi jste zvítězili nad zlým čarodějem a teď si můžete buď odvést princeznu anebo si vybrat některý z krásných zlatých předmětů, které kouzelník vlastní. Princezna se vám nelíbí, proto jste se rozhodl pro zlato. Můžete si vybrat spoustu velkých a krásných předmětů, jedinou podmínkou je, že vybrané objekty musíte být schopen odnést v batohu, jehož nosnost (i vaše, koneckonců) je omezena. Pokud se vám to nepovede, nezískáte nic. Předměty jsou různorodé – svícny, sošky apod., každý stojí jinak a váží jinak.  Teď se vám hodí praxe v dynamickém programování z PRO.

Váš úkol založený na tomto příběhu je následující:

Vstupem je množina položek P={p₁,p₂,...,p_n}, kde položka p_i má velikost s_i a hodnotu v_i, batohová kapacita (tj. velikost batohu) je C. Vašim úkolem je najít podmnožinu s maximální hodnotou zjištěnou jako součet hodnot prvků podmnožiny takovou, aby součet velikostí prvků podmnožiny nepřekročil C (tj. všechny vybrané položky se musí vejít do batohu). Velikosti položek i jejich hodnoty jsou kladná čísla do 1000.

1. Vyřešte tuto úlohu jednoduchým, jasným a správným greedy algoritmem za 4 body.
2. Vyřešte úlohu správným algoritmem na principu DP za 8 bodů.

Vzhledem k tomu, že stručný popis řešení byl probírán, jde tentokrát o vyloženě programátorskou úlohu, tj. neodevzdáváte tentokrát jen popis algoritmu, ale též  program – zdrojový text, sputitelnou verzi, vzorová data, dokumentaci. Tentokrát není možné získat body za prezentaci, pouze body za pořadí, pokud bude odevzdáno dostatek prací.