Teoretický úvod je v plném znění k nalezení zde.
Princip tohoto řešení je rozložení problému na menší. Využívá se toho, že je-li řešení problému s k věcmi a nosností N optimální a obsahuje k-tou věc, pak optimální řešení problému s prvními k-1 věcmi a nosností (N - váha k) je toto řešení po vyjmutí k-té věci. Výhoda DP spočívá v tom, že si pamatujeme co jsme již počítali a nepočítáme to znovu.
Algoritmus je vylepšená metoda řešení hrubou silou. Vylepšení spočívá v tom, že jsou prozkoumávány pouze ty větve, které ještě potenciálně mohou přinést lepší řešení, než nejlepší dosud nalezené. Potenciální cena řešení při prozkoumávání i-té věci je součet cen věcí, které už při procházení této větve v batohu jsou a cen všech věcí, které v této větvi ještě nebyly prozkoumány a tedy mohou potenciálně být v řešení.
Jedná se o stejný algoritmus jako v první úloze, předměty se seřadí podle klesajícího poměru cena / váha a předměty které se ještě vejdou do batohu se postupně přidávají.
zadání | DP | BB | HR | |||
cena | kroky | cena | kroky | cena | kroky | |
4 | 352 | 400 | 352 | 12 | 342 | 3 |
10 | 1125 | 1000 | 1125 | 146 | 1104 | 8 |
15 | 1814 | 3000 | 1814 | 178 | 1808 | 14 |
20 | 2335 | 5000 | 2335 | 3491 | 2322 | 17 |
22 | 2501 | 5500 | 2501 | 12755 | 2481 | 17 |
25 | 2954 | 7500 | 2954 | 33225 | 2941 | 20 |
27 | 3143 | 9450 | 3143 | 38631 | 3131 | 22 |
30 | 3581 | 12000 | 3581 | 184291 | 3565 | 24 |
32 | 3694 | 14400 | 3694 | 263077 | 3684 | 26 |
35 | 4081 | 17500 | 4081 | 677279 | 4071 | 28 |
37 | 4222 | 20350 | 4222 | 721623 | 4213 | 29 |
40 | 4628 | 24000 | 4628 | 8576258 | 4621 | 31 |
Z tabulky je vidět, že všechny tři metody dávají zhruba stejnou cenu řešení. Heuristika dává průměrně nižší ceny než zbylé dvě metody, to ovšem za cenu řádově menšího počtu kroků nutných k nalezení řešení. Jako nejhorší z hlediska počtu kroků se jeví metoda větví a hranic, počet kroků u ní s množstvím věcí neúměrně roste. Nejmenší počet kroků potřebuje heuristika, u ní je počet kroků řádově srovnatelný s počtem věcí (je o něco menší, protože pokud je batoh již plný, nepokračuje se v hledání dalších předmětů, jinak by byl počet kroků roven počtu předmětů).
Třída pro práci s batohem
cpp
html
Třída pro čtení vstupu
cpp
html
Hlavní program a jednotlivé algoritmy
cpp
html