Bevezetés
Lhakpa serpa hegyi vezető és teherhordó.
Több hónapos gondos tervezés után mindjárt útnak indul az az expedíció, amelynek Lhakpa dolgozik.
Azért az értékért kap fizetést, amit felvitt a bázistáborba.
Előtte sok tárgy sorakozik, mindegyiknek megvan az értéke és a súlya.
Lhakpa szívesen elvinné az összes tárgyat, de a hátizsákjába csak korlátozott súly fér bele.
Utasítások
A feladatod meghatározni, hogy mely tárgyakat vigye magával Lhakpa, hogy a kiválasztott tárgyak összértéke a lehető legnagyobb legyen, figyelembe véve a hátizsák teherbírását.
A tárgyakat egy lista formájában kapod meg.
Minden tárgynak van súlya és értéke.
A megadott értékek mind szigorúan pozitívak.
Lhakpa minden tárgyból csak egyet vihet el.
Például:
Items: [
{ "weight": 5, "value": 10 },
{ "weight": 4, "value": 40 },
{ "weight": 6, "value": 30 },
{ "weight": 4, "value": 50 }
]
Knapsack Maximum Weight: 10
A fenti példában az első tárgy súlya 5, értéke 10, a második tárgy súlya 4, értéke 40, és így tovább.
Ebben a példában Lhakpának a második és a negyedik tárgyat kell elvinnie, hogy maximalizálja az értéket, ami ebben az esetben 90.
Nem szerezhet 90-nél többet, mert a hátizsákjának a súlykorlátja 10.
WebAssembly-specifikus megjegyzések
A tárgyak a lineáris memórián keresztül érkeznek, az első tárgy a 0 eltoláson van.
Minden tárgyat két 32 bites egész számból álló pár reprezentál.
A pár első száma a súly, a második pedig az érték.
Vegyünk például egy két tárgyból álló listát, ahol az elsőnél weight=1, value=2, a másodiknál pedig weight=5, value=8.
A lista ekkor így nézne ki a memóriában:
| 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 |
| - item 1 weight - | -- item 1 value - | - item 2 weight - | -- item 2 value - |
|0x01,0x00,0x00,0x00|0x02,0x00,0x00,0x00|0x05,0x00,0x00,0x00|0x08,0x00,0x00,0x00|
Ha úgy döntesz, felülírhatod a bemenethez használt lineáris memória címeit.
