How to resolve the algorithm Knapsack problem/0-1 step by step in the Emacs Lisp programming language

Published on 12 May 2024 09:40 PM
#Emacs lisp

How to resolve the algorithm Knapsack problem/0-1 step by step in the Emacs 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 to pack well for the trip. He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it,   and it will have to last the whole day. He creates a list of what he wants to bring for the trip but the total weight of all items is too much. He then decides to add columns to his initial list detailing their weights and a numerical value representing how important the item is for the trip.

Here is the list:

The tourist can choose to take any combination of items from the list, but only one of each item is available. He may not cut or diminish the items, so he can only take whole units of any item.

Show which items the tourist can carry in his knapsack so that their total weight does not exceed 400 dag [4 kg],   and their total value is maximized. [dag = decagram = 10 grams]

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Knapsack problem/0-1 step by step in the Emacs Lisp programming language

Source code in the emacs programming language

(defun ks (max-w items)
  (let ((cache (make-vector (1+ (length items)) nil)))
    (dotimes (n (1+ (length items)))
      (setf (aref cache n) (make-hash-table :test 'eql)))  
    (defun ks-emb (spc items)
      (let ((slot (gethash spc (aref cache (length items)))))
        (cond 
         ((null items) (list 0 0 '()))
         (slot slot)
         (t (puthash spc 
                  (let*
                      ((i (car items))
                       (w (nth 1 i))
                       (v (nth 2 i))
                       (x (ks-emb spc (cdr items))))
                    (cond 
                     ((> w spc) x)
                     (t
                      (let* ((y (ks-emb (- spc w) (cdr items)))
                             (v (+ v (car y))))
                        (cond 
                         ((< v (car x)) x)
                         (t 
                          (list v (+ w (nth 1 y)) (cons i (nth 2 y)))))))))
                  (aref cache (length items)))))))
    (ks-emb max-w items)))

(ks 400
    '((map 9 150) (compass 13 35) (water 153 200) (sandwich 50 160)
      (glucose 15 60) (tin 68 45)(banana 27 60) (apple 39 40)
      (cheese 23 30) (beer 52 10) (cream 11 70) (camera 32 30)
      (T-shirt 24 15) (trousers 48 10) (umbrella 73 40)
      (waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)
      (glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)))


(defun best-rate (l1 l2)
  "predicate for sorting a list of elements regarding the value/weight rate"
  (let*
      ((r1 (/ (* 1.0 (nth 2 l1)) (nth 1 l1)))
       (r2 (/ (* 1.0 (nth 2 l2)) (nth 1 l2))))
    (cond
     ((> r1 r2) t)
     (t nil))))

(defun ks1 (l max)
  "return a complete list - complete means 'less than max-weight
but add the next element is impossible'"
(let ((l (sort l 'best-rate)))
  (cond
   ((null l) l)
   ((<= (nth 1 (car l)) max) 
    (cons (car l) (ks1 (cdr l) (- max (nth 1 (car l))))))
   (t (ks1 (cdr l) max)))))

(defun totval (lol)
  "totalize values of a list - lol is not for laughing 
but for list of list"
  (cond 
   ((null lol) 0)
   (t
    (+
     (nth 2 (car lol))
     (totval (cdr lol))))))

(defun ks (l max)
  "browse the list to find the best subset to put in the f***ing knapsack"
    (cond
     ((null (cdr l)) (list (car l)))
     (t
      (let*
          ((x (ks1 l max))
           (y (ks (cdr l) max)))
        (cond
         ((> (totval x) (totval y)) x)
         (t y))))))

        (ks '((map 9 150) (compass 13 35) (water 153 200) (sandwich 50 160)
              (glucose 15 60) (tin 68 45)(banana 27 60) (apple 39 40)
              (cheese 23 30) (beer 52 10) (cream 11 70) (camera 32 30)
              (T-shirt 24 15) (trousers 48 10) (umbrella 73 40)
              (waterproof-trousers 42 70) (overclothes 43 75) (notecase 22 80)
              (glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)) 400)

You may also check:How to resolve the algorithm Biorhythms step by step in the Delphi programming language
You may also check:How to resolve the algorithm Day of the week step by step in the CLU programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Lambdatalk programming language
You may also check:How to resolve the algorithm Runtime evaluation step by step in the Frink programming language
You may also check:How to resolve the algorithm Permutations step by step in the Erlang programming language