Problém batohu

Deadline: 30. března 2025

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. Důležité je rozmyslet si co nejlepší a nejefektivnější přístup k tomuto problému.

Dostanete čtyři soubory specifikující vstup. Každý z těchto souborů obsahuje určité 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, resp. alespoň nastavit co nejlepší hodnoty hyperparametrů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í. A nastavení hyperparametrů by mělo být zdůvodněné, tedy mělo by být řečeno, proč si myslíte, že daná hodnota je dobrá pro řešení problému. Odpověď stylu "našel jsem to pomocí experimentů" není dostačující. Určitě tak vhodnou hodnotu můžete zkusit najít, když se vám to povede, ale měli byste se ji pokusit pak alespoň zpětně odůvodnit.)

Vámi odevzdané řešení by mělo obsahovat:

• Popis algoritmu (kódování jedince, genetické operátory, způsob selekce, zvolené hodnoty hyperparametrů a jejich zdůvodnění etc.).
• Kód algoritmu pro případnou kontrolu - výrazně preferuji, když bude algoritmus popsán dost dobře a nebudu muset pro pochopení nazírat do kódu. (Zmenší se tak i pravděpodobnost, že Vám v kódu najdu případnou chybu.)
• Graf toho, jak se měnila fitness v průběhu generací.
• Nejlepší řešení, které jste objevili (hlavně tedy jeho cena).