Problém batohu

Deadline - 4. dubna 2024

Je dána množina $n$ objektů s váhami $w_i$ a cenami $c_i$. Cílem v problému batohu je najít takovou podmnožinu těchto objektů maximalizující kumulativní cenu (tedy součet cen objektů v této podmnožině), že jejich společná váha (tedy součet vah objektů v podmnožině) je menší nebo rovna zadanému limitu $W$.

Úkolem je implementovat evoluční algoritmus řešící tento problém. Můžete buď naprogramovat celý algoritmus od začátku, nebo klidně využít něco z toho, co jsme implementovali na cvičeních.

Dostanete čtyři soubory specifikující vstup. Každý z těchto souborů obsahuje množství řádků. První řádek obsahuje dvě čísla, a to množství objektů $n$ a kapacitu batohu $W$. Pak následuje $n$ řádků, na každém je cena $c_i$ a váha $w_i$ jednoho objektu. Hodnoty na jednotlivých řádcích jsou odděleny mezerou.

Pro vstupní soubory debug_10.txt a debug_20.txt je kumulativní cena optimálního řešení 295, respektive 1024. Této znalosti můžete využít ke kontrole korektnosti a k ladění své implementace. Vaším cílem je pak najít co nejlepší řešení (kumulativní cenu podmnožiny) pro soubory input_100.txt a input_1000.txt. (Snažte se tedy sestavit celý evoluční algoritmus z co nejlepších a nejvhodnějších částí pro daný problém, abyste opravdu našli dost dobré řešení. Naivní implementace využívající základních verzí všech částí algoritmu nebude dostačující.)

Řešení mi odevzdávejte na můj mail. Vámi odevzdané řešení by mělo obsahovat:

• Popis algoritmu (kódování jedince, genetické operátory, způsob selekce etc.)
• Kód algoritmu pro případnou kontrolu
• Graf toho, jak se měnila fitness v průběhu generací
• Nejlepší řešení, které jste objevili (hlavně jeho cena)