Hátizsák

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.

Megvalósítás

Az elemeket rekordok képviselik, amelyek az item.lfe fájlban vannak definiálva. A súly lekéréséhez használd az item-weight, az érték lekéréséhez pedig az item-value függvényt.

;; Create an item with weight=5, value=50
(set item (make-item weight 5 value 50))

;; Get the weight. Returns 5.
(item-weight item)

;; Get the value. Returns 50.
(item-value item)

---

Forrás

Wikipedia