CD kompilace

• Data: cd_data.zip

Kdybychom měli k úloze přistupovat jako k černé skříňce, neměli byste informace o délkách skladeb využívat nikde jinde než v ohodnocovací funkci. V této úloze ale je povoleno využívat či analyzovat délky skladeb i jinde, např. v rekombinačních operátorech.

Rocková skupina XY chce na sklonku kariéry vydat soubornou kompilaci všech svých vypalovaček. Problém je, jak skladby optimálně rozvrhnout na co nejmenší počet CD nosičů stejné kapacity C.

Cílem je vměstnat všechny skladby na co nejmenší počet disků.

• Vstupy:
  • N skladeb, každá skladba má svoji délku v sekundách.
  • Jednotná kapacita disků C.
• Výstup: Počet použitých disků M, na kterých jsou uloženy všechny požadované skladby včetně údaje o průměru kvadrátů zaplněnosti použitých disků.

• Seznam lineárních řetězců celých čísel, kde každý řetězec reprezentuje jeden disk a čísla v řetězci udávají identifikátory skladeb.
• Dva seznamy – seznam (permutace) skladeb, seznam rozdělujících bodů (pozice v rámci seznamu skladeb, které vymezují jednotlivé disky).[permutace skladeb][break-pointy]
• …

Celková zaplněnost disků

<latex> \begin{equation*} f(s) = \frac{\sum_{i=1}^M \left(\frac{z_i}{C}\right)^2}{M} \end{equation*} </latex>

kde <latex>z_i</latex> je zaplněnost i-tého CD. Tato funkce je maximalizována.