core.clj

(ns knapsack.core
  (:require [clojure.string :as s]))

(def item-data
  ["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])

(defstruct item :name :weight :value)

(def items (vec (map #(apply struct item %) (partition 3 item-data))))

(declare mm)

(defn m [index weight]
  (cond
    (< index 0) [0 []]
    (= weight 0) [0 []]
    :else
    (let [{item-weight :weight item-value :value} (get items index)]
      (if (> item-weight weight)
        (mm (dec index) weight)
        (let [[vn sn :as no] (mm (dec index) weight)
              [vy sy :as yes] (mm (dec index) (- weight item-weight))]
          (if (> (+ vy item-value) vn)
            [(+ vy item-value) (conj sy index)]
            no))))))

(def mm (memoize m))

(defn calc [budget]
  (let [[value indexes] (m (-> items count dec) budget)
        names (map (comp :name items) indexes)]
    (println "items to pack:" (s/join ", " names))
    (println "total value:" value)
    (println "total weight:" (reduce + (map (comp :weight items) indexes)))))