Newer
Older
## Knapsack problem
Máme n předmětů, kde každý má danou váhu a danou hodnotu. Dále máme
batoh o dané nostnosti. Problém spočívá v nalezní nejhodnotnější kombinace
předmětů, které batoh unese. Výsledek je hodnota vybraných předmětů a také
seznam těchto předmětů.
## Implementace
Program bere argumenty v tomto pořadí:
<br><počet předmětů(n)> n*<hodnota předmětu> n*<váha předmětů>
<br>Hodnoty číselné a mezi nimi mezera.
<br>V repozitři je soubor exmpData s ukázkovými argumenty.
Pro výpočet jsem zvolil postup, kde postupně vypočítáme optimální hodnotu pro všechny kombinace.
Toho dosáhneme tak, že si vytvořímě matici velikosti (počet prvků + 1) * (nostnost batohu + 1)
a postupně vypočítáváme optimální hodnoty pro každou kombinaci až dokončíme celou matice.
Z matice nakonec zjistíme jaká je optimální hondota a kombinace předmětů.
Jednovláková implementace postupuje podle postupu viz. výše.
<br>Více vláknová implementace postupuje také podle postupu viz. výše, ale
výpočet řádku matice rozdělý mezi dostupný počet vláken.
## Měření
Měření jsem provedl na:
Processor Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz, 2701 Mhz, 2 Core(s), 4 Logical Processor(s)
<br>V repozitři je sada testů timeCheck, kterými jsem získal data.
Z měření vyplývá, že implementace, kterou jsem zvolil, je vhodná prováděd vícevláknově, pokud máme menší počet prvků a velikou nostnost batohu.
## Výsledky měření
|nostnost|počet předmětů|ST (ms)|MT (ms)|
|---|---|:-:|---|
|10 |10| 0 | 59|
|100|20| 0 | 24|
|200|40| 3| 29|
|1000 |80| 31| 55 |
|5000 |100| 186| 157 |
|10000 |200| 758| 538 |
|100000 |500| 18813| 13063 |
|100000 |2000| 68202| 46080|
ERBEN JAROSLAV 2019