(scroll down for English)
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 řešení (kumulativní cenu podmnožiny) pro soubory input_100.txt a input_1000.txt.
Řešení mi odevzdávejte na mail. Vámi odevzdané řešení by mělo obsahovat:
Hodnocení: a) Najděte nejlepší řešení pro debug_10.txt a debug_20.txt b) Co nejlepší výsledek pro input100.txt a input1000.txt b*) (I relativně slabé výsledky mohou projít, pokud je řešení dobře zdokumentované a zkusili jste a zdokumentovali několik variant nastavení algoritmu - hyperparams, různé operátory/fitness…)
A set of \(n\) objects is given with weights \(w_i\) and prices \(c_i\). The goal in the knapsack problem is to find a subset of these objects that maximizes the cumulative price (i.e., the sum of the prices of objects in this subset), such that their total weight (i.e., the sum of the weights of objects in the subset) is less than or equal to a given limit \(W\).
The task is to implement an evolutionary algorithm to solve this problem. You can either program the entire algorithm from scratch or use something we implemented in the exercises.
You will receive four files specifying the input. Each of these files contains several lines. The first line contains two numbers: the number of objects $n$ and the capacity of the knapsack \(W\). Then there are \(n\) lines, each containing the price \(c_i\) and weight \(w_i\) of one object. The values on individual lines are separated by a space.
For the input files debug_10.txt and debug_20.txt, the cumulative price of the optimal solution is 295 and 1024, respectively. You can use this knowledge to check the correctness and debug your implementation. Your goal is then to find the solution (cumulative price of the subset) for the files input_100.txt and input_1000.txt.
Submit your solution via email. Your submitted solution should include:
Evaluation criteria a) Find the best solution for debug_10.txt and debug_20.txt b) A good score on input100.txt input1000.txt b*) (Even relatively weak results can pass if the solution is well-documented, and you tried and documented several settings of the algorithm - hyperparams, different operators/fitness…)