knapsack.clj

(defn calc-max-value [i w items]
  ;; if either num items or capacity is zero max value is zero!
  (if (or (= i 0) (= w 0))
    0
    (let [curr-item (get items (- i 1))
          prev-max-value (calc-max-value (- i 1) (- w (:weight curr-item)) items)
          max-value-without-me (calc-max-value (- i 1) w items)
          potential-value-with-me (+ (:value curr-item) prev-max-value)
          ]
      (if (<= (:weight curr-item) w)
        ;; current item weight will not exceed knapsack capacity
        ;; take the larger of value with current item and
        ;; value without current item
        (if (> potential-value-with-me max-value-without-me)
          potential-value-with-me
          max-value-without-me)

        ;; current item weight exceeds knapsack capacity so take
        ;; max value without current item
        max-value-without-me ))))

(defn solve-knapsack [n w items]
  (let [find-max (memoize calc-max-value)]
    (loop [i n
           k w
           knapsack []]
      (let [curr-item (get items (- i 1))]
        ;; base case, return the knapsack contents so far
        (if (or (= 0 k) (= 0 i))
          knapsack
          (if (not= (find-max i k items) (find-max (- i 1) k items))
            (recur (- i 1) (- k (:weight curr-item)) (conj knapsack curr-item))
            (recur (- i 1) k knapsack )))))))