Skip to content
Snippets Groups Projects
README.md 1.84 KiB
Newer Older
Jaroslav Erben's avatar
Jaroslav Erben committed
# PJC-Knapsack-Problem

Jaroslav Erben's avatar
Jaroslav Erben committed
## 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)
Jaroslav Erben's avatar
Jaroslav Erben committed
a postupně vypočítáváme optimální hodnoty pro každou kombinaci až dokončíme celou matice.
Jaroslav Erben's avatar
Jaroslav Erben committed
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)
Jaroslav Erben's avatar
Jaroslav Erben committed
<br> VisualStudio 2017
<br> ReleaseModu
Jaroslav Erben's avatar
Jaroslav Erben committed
<br>V repozitři je sada testů timeCheck, kterými jsem získal data.
Jaroslav Erben's avatar
Jaroslav Erben committed

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