Рюкзак

Вказівки

Визначте, які предмети взяти, щоб загальна цінність її вибору була максимальною, зважаючи на вантажопідйомність рюкзака.

Предмети буде представлено як масив предметів. Кожен предмет матиме вагу та цінність. Усі наведені значення будуть строго додатними. Lhakpa може взяти лише по одному предмету кожного виду.

Наприклад:

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

Knapsack Maximum Weight: 10

У наведеному прикладі перший предмет має вагу 5 і цінність 10, другий предмет має вагу 4 і цінність 40, і так далі. У цьому прикладі Lhakpa має взяти другий і четвертий предмети, щоб максимізувати свою цінність, яка в цьому випадку дорівнює 90. Вона не може отримати більше ніж 90, оскільки її рюкзак має обмеження ваги 10.

Реалізація

Предмети представлено записами, визначеними у item.lfe. Використайте item-weight, щоб отримати вагу, та item-value, щоб отримати значення.

;; 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)

---

Джерело

Wikipedia