Knapsack – problém batoha

Úloha: Knapsack na Exercisme

Čo sa v cvičení naučíte

Po vyriešení cvičenia budete vedieť:

• preložiť slovný opis optimalizačného problému do algoritmu,
• rozpoznať problém 0/1 batoha – každý predmet možno vybrať alebo nevybrať, ale nemožno ho použiť viackrát,
• rozdeliť problém na menšie podproblémy podľa dostupnej kapacity,
• navrhnúť stav dynamického programovania a prechod medzi stavmi,
• vypočítať najväčšiu dosiahnuteľnú hodnotu bez prekročenia hmotnostného limitu,
• pracovať so zoznamom slovníkov, v ktorých sú údaje weight a value,
• porovnať rekurzívne riešenie, memoizáciu a tabuľkové dynamické programovanie,
• odhadnúť časovú a pamäťovú zložitosť algoritmu,
• čítať testy ako súčasť špecifikácie funkcie a vracať výsledok pomocou return.

Čo si musíte preštudovať

Pred riešením si zopakujte najmä tieto témy:

• funkcie, parametre, návratová hodnota a lokálne premenné,
• zoznamy, indexovanie, range() a vnorené cykly,
• slovníky a prístup k hodnotám pomocou kľúčov,
• podmienky if a porovnávacie operátory,
• maximum z viacerých hodnôt pomocou max(),
• rozdiel medzi obyčajným delením / a celým delením //, ak si budete počítať indexy alebo kapacity,
• rekurzia a podmienka ukončenia,
• memoizácia a dynamické programovanie,
• časová a priestorová zložitosť algoritmov.

Užitočné kapitoly v oficiálnom Python manuáli:

• Python Tutorial,
• definovanie funkcií,
• riadiace štruktúry – if, for a range(),
• zoznamy a indexovanie,
• slovníky,
• typy list a dict,
• vstavaná funkcia max() ,
• príkaz return,
• definovanie a volanie výnimiek,
• dekorátor functools.cache , ak chcete skúsiť rekurzívnu verziu s memoizáciou.

Porozumejte zadaniu

Prečítajte si celé zadanie na Exercisme. Funkcia dostane maximálnu hmotnosť batoha a zoznam predmetov. Každý predmet má hmotnosť weight a hodnotu value. Výsledkom má byť najväčšia celková hodnota predmetov, ktorých súčet hmotností neprekročí limit.

Napríklad pre:

items = [
    {"weight": 5, "value": 10},
    {"weight": 4, "value": 40},
    {"weight": 6, "value": 30},
    {"weight": 4, "value": 50},
]

pri limite 10 vyberieme druhý a štvrtý predmet. Ich hmotnosť je 8 a hodnota 90. Lepšia prípustná kombinácia neexistuje, preto funkcia vráti 90.

Nezamieňajte si dve pravidlá:

• predmet môžeme vziať celý alebo ho vynechať – nie jeho časť,
• každý predmet môžeme použiť najviac raz.

Ako problém rozložiť

Najprv si definujte stav. Označme best[c] najväčšiu hodnotu, ktorú vieme dosiahnuť s kapacitou c po spracovaní doteraz prečítaných predmetov. Na začiatku nepoznáme žiadny predmet, preto je hodnota pre každú kapacitu nula.

Pri spracovaní predmetu s hmotnosťou w a hodnotou v máte dve možnosti:

1. predmet nevziať – najlepšia hodnota zostane taká, aká bola,
2. predmet vziať – k najlepšiemu výsledku pre kapacitu c - w pripočítate v.

Pre kapacitu aspoň w teda porovnávate:

best[c] = max(best[c], best[c - w] + v)

Ak je c < w, predmet sa do batoha nezmestí a stav nemeníte.

Dôležité poradie prepočítavania

Pri jednorozmernom zozname prechádzajte kapacity od maximum_weight smerom dole po w:

maximum_weight, maximum_weight - 1, ..., w

Tým zabezpečíte, že best[c - w] ešte pochádza z predchádzajúcich predmetov. Keby ste kapacity prechádzali od menších k väčším, v tom istom priechode by ste mohli práve spracovaný predmet použiť znova. Vyriešili by ste iný problém – neobmedzený batoh.

Odporúčaný postup riešenia

1. Otvorte si pripravený súbor v Exercisme a overte presný názov funkcie a poradie jej parametrov.
2. Zistite, aké hodnoty majú maximum_weight, item["weight"] a item["value"].
3. Vytvorte zoznam best dĺžky maximum_weight + 1, vyplnený nulami.
4. Pre každý predmet získajte jeho hmotnosť a hodnotu.
5. Kapacitu prechádzajte zostupne a aktualizujte najlepšiu hodnotu pomocou voľby „nevziať alebo vziať“.
6. Vráťte hodnotu best[maximum_weight].
7. Spustite testy po každej podstatnej zmene a riešenie zjednodušte až vtedy, keď rozumiete jeho invariantu.

Alternatívou je dvojrozmerná tabuľka, v ktorej riadok predstavuje počet spracovaných predmetov a stĺpec kapacitu. Je názorná, ale používa viac pamäte. Jednorozmerné riešenie používa čas O(n * W) a pamäť O(W), kde n je počet predmetov a W maximálna kapacita batoha.

Kontrolné príklady

Pred odovzdaním si skúste ručne vysvetliť tieto prípady:

maximum_value(0, [{"weight": 1, "value": 10}])
# 0

maximum_value(10, [])
# 0

maximum_value(10, [
    {"weight": 5, "value": 10},
    {"weight": 4, "value": 40},
    {"weight": 6, "value": 30},
    {"weight": 4, "value": 50},
])
# 90

Overte si aj predmet ťažší než celý batoh, viac predmetov s rovnakou hmotnosťou, prípad, keď sa zmestia všetky predmety, a prípad, keď je výhodné vynechať predmet s veľkou hmotnosťou a malou hodnotou. Funkcia nemá nič vypisovať pomocou print; automatické testy kontrolujú jej návratovú hodnotu.

Ďalšie úlohy na precvičenie

• Pascal's Triangle
• Killer Sudoku Helper
• Fibonacci

Previous Post Next Post