29 lines
1.2 KiB
Common Lisp
29 lines
1.2 KiB
Common Lisp
(defstruct item
|
|
(name nil :type string)
|
|
(weight nil :type real)
|
|
(price nil :type real))
|
|
|
|
(defun price-per-weight (item)
|
|
(/ (item-price item) (item-weight item)))
|
|
|
|
(defun knapsack (items total-weight)
|
|
(loop with sorted = (sort items #'> :key #'price-per-weight)
|
|
while (plusp total-weight)
|
|
for item in sorted
|
|
for amount = (min (item-weight item) total-weight)
|
|
collect (list (item-name item) amount)
|
|
do (decf total-weight amount)))
|
|
|
|
(defun main ()
|
|
(let ((items (list (make-item :name "beef" :weight 3.8 :price 36)
|
|
(make-item :name "pork" :weight 5.4 :price 43)
|
|
(make-item :name "ham" :weight 3.6 :price 90)
|
|
(make-item :name "greaves" :weight 2.4 :price 45)
|
|
(make-item :name "flitch" :weight 4.0 :price 30)
|
|
(make-item :name "brawn" :weight 2.5 :price 56)
|
|
(make-item :name "welt" :weight 3.7 :price 67)
|
|
(make-item :name "salami" :weight 3.0 :price 95)
|
|
(make-item :name "sausage" :weight 5.9 :price 98))))
|
|
(loop for (name amount) in (knapsack items 15)
|
|
do (format t "~8A: ~,2F kg~%" name amount))))
|