Hátizsák

Utasítások

A feladatod meghatározni, hogy mely tárgyakat vigye magával Bob, 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árgyak egy listában lesznek megadva. Minden tárgynak van súlya és értéke. A megadott értékek mindig szigorúan pozitívak. Bob 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 fentiekben 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 Bobnak a második és a negyedik tárgyat kell elvinnie, hogy maximalizálja az értéket, ami ebben az esetben 90. Nem kaphat 90-nél többet, mivel a hátizsákjának súlykorlátja 10.

---

Forrás

Wikipedia