How to resolve the algorithm Knapsack problem/Bounded step by step in the Common Lisp programming language
How to resolve the algorithm Knapsack problem/Bounded step by step in the Common Lisp programming language
Table of Contents
Problem Statement
A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature. So he needs some items during the trip. Food, clothing, etc. He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening. He creates a list of what he wants to bring for the trip, but the total weight of all items is too much. He adds a value to each item. The value represents how important the thing for the tourist. The list contains which items are the wanted things for the trip, what is the weight and value of an item, and how many units does he have from each items.
This is the list:
The tourist can choose to take any combination of items from the list, and some number of each item is available (see the column piece(s) in the list above). He may not cut the items, so he can only take whole units of any item.
Show which items does the tourist carry in his knapsack so that their total weight does not exceed 4 kg, and their total value is maximized.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Knapsack problem/Bounded step by step in the Common Lisp programming language
Source code in the common programming language
;;; memoize
(defmacro mm-set (p v) `(if ,p ,p (setf ,p ,v)))
(defun knapsack (max-weight items)
(let ((cache (make-array (list (1+ max-weight) (1+ (length items)))
:initial-element nil)))
(labels ((knapsack1 (spc items)
(if (not items) (return-from knapsack1 (list 0 0 '())))
(mm-set (aref cache spc (length items))
(let* ((i (first items))
(w (second i))
(v (third i))
(x (knapsack1 spc (cdr items))))
(loop for cnt from 1 to (fourth i) do
(let ((w (* cnt w)) (v (* cnt v)))
(if (>= spc w)
(let ((y (knapsack1 (- spc w) (cdr items))))
(if (> (+ (first y) v) (first x))
(setf x (list (+ (first y) v)
(+ (second y) w)
(cons (list (first i) cnt) (third y)))))))))
x))))
(knapsack1 max-weight items))))
(print
(knapsack 400
'((map 9 150 1) (compass 13 35 1) (water 153 200 2) (sandwich 50 60 2)
(glucose 15 60 2) (tin 68 45 3) (banana 27 60 3) (apple 39 40 3)
(cheese 23 30 1) (beer 52 10 3) (cream 11 70 1) (camera 32 30 1)
(T-shirt 24 15 2) (trousers 48 10 2) (umbrella 73 40 1)
(trousers 42 70 1) (overclothes 43 75 1) (notecase 22 80 1)
(glasses 7 20 1) (towel 18 12 2) (socks 4 50 1) (book 30 10 2))))
You may also check:How to resolve the algorithm Hello world/Text step by step in the REALbasic programming language
You may also check:How to resolve the algorithm String case step by step in the Avail programming language
You may also check:How to resolve the algorithm Array concatenation step by step in the VBA programming language
You may also check:How to resolve the algorithm Nth root step by step in the M2000 Interpreter programming language
You may also check:How to resolve the algorithm Sorting algorithms/Heapsort step by step in the Python programming language