knapsack.clj

; doll_smuggler in Clojure

(defstruct doll :ident :weight :value)

(def dolls [
  (struct doll "luke" 9 150)
  (struct doll "anthony" 13  35)
  (struct doll "candice" 153 200)
  (struct doll "dorothy" 50 160)
  (struct doll "puppy" 15 60)
  (struct doll "thomas" 68 45 )
  (struct doll "randal" 27 60 )
  (struct doll "april" 39 40 )
  (struct doll "nancy" 23 30 )
  (struct doll "bonnie" 52 10 )
  (struct doll "marc" 11 70 )
  (struct doll "kate" 32 30 )
  (struct doll "tbone" 24 15 )
  (struct doll "tranny" 48 10 )
  (struct doll "uma" 73 40 )
  (struct doll "grumpkin" 42 70 )
  (struct doll "dusty" 43 75 )
  (struct doll "grumpy" 22 80 )
  (struct doll "eddie" 7 20 )
  (struct doll "tory" 18 12 )
  (struct doll "sally" 4 50 )
  (struct doll "babe" 30 10 )])

; Pack the dolls
(defn pack [knapsack i capacity]
  (if (or (< i 0)
          (= capacity 0))
    [[] 0]
    (let [{doll-weight :weight doll-value :value} (get knapsack i)]
      (if (> doll-weight capacity)
        (pack knapsack (dec i) capacity)
        (let [[knapsack-packed val-packed] 
                (pack knapsack (dec i) (- capacity doll-weight))
              [knapsack-not-packed val-not-packed]
                (pack knapsack (dec i) capacity)]
          (if (> (+ val-packed doll-value) val-not-packed)
            [(conj knapsack-packed (get knapsack i)) (+ val-packed doll-value)]
            [knapsack-not-packed val-not-packed]))))))

; Replace pack with memoized pack using core.memoize
(def pack (memoize pack))

(println (pack dolls (dec (count dolls)) 400))

knapsack.coffee

# doll_smuggler in CoffeeScript

dolls = [
  ['luke', 9, 150],
  ['anthony', 13,  35],
  ['candice', 153, 200],
  ['dorothy', 50, 160],
  ['puppy', 15, 60],
  ['thomas', 68, 45],
  ['randal', 27, 60],
  ['april', 39, 40],
  ['nancy', 23, 30],
  ['bonnie', 52, 10],
  ['marc', 11, 70],
  ['kate', 32, 30],
  ['tbone', 24, 15],
  ['tranny', 48, 10],
  ['uma', 73, 40],
  ['grumpkin', 42, 70],
  ['dusty', 43, 75],
  ['grumpy', 22, 80],
  ['eddie', 7, 20],
  ['tory', 18, 12],
  ['sally', 4, 50],
  ['babe', 30, 10]
]

pack = (knapsack, i, capacity) ->
  return [[], 0] unless i >= 0 and capacity > 0
  doll = name: knapsack[i][0], weight: knapsack[i][1], value: knapsack[i][2]
  return pack(knapsack, i - 1, capacity) if doll.weight >= capacity
  [knapsackPacked, valPacked] = pack(knapsack, i - 1, capacity - doll.weight)
  [knapsackNotPacked, valNotPacked] = pack(knapsack, i - 1, capacity)
  if (valPacked + doll.value) > valNotPacked
    knapsackPacked.unshift [doll.name, doll.weight, doll.value]
    return [knapsackPacked, valPacked + doll.value]
  [knapsackNotPacked, valNotPacked]

memoize = (func) ->
  memo = {}
  -> 
    k = JSON.stringify arguments
    if k of memo then memo[k] else
      (memo[k] = func.apply(@, arguments))

#[knapsack, val] = (pack = memoize pack) dolls, dolls.length - 1, 400
[knapsack, val] = pack dolls, dolls.length - 1, 400
console.log 
  knapsack: knapsack, 
  weight: (d[1] for d in knapsack).reduce (d, s) -> d + s
  value: (d[2] for d in knapsack).reduce (d, s) -> d + s

knapsack.fs

// doll_smuggler in F#

open System
open System.Collections.Generic

let dolls = [
    ("luke",      9, 150);
    ("anthony",  13,  35);
    ("candice", 153, 200);
    ("dorothy",  50, 160);
    ("puppy",    15,  60);
    ("thomas",   68,  45);
    ("randal",   27,  60);
    ("april",    39,  40);
    ("nancy",    23,  30);
    ("bonnie",   52,  10);
    ("marc",     11,  70);
    ("kate",     32,  30);
    ("tbone",    24,  15);
    ("tranny",   48,  10);
    ("uma",      73,  40);
    ("grumpkin", 42,  70);
    ("dusty",    43,  75);
    ("grumpy",   22,  80);
    ("eddie",     7,  20);
    ("tory",     18,  12);
    ("sally",     4,  50);
    ("babe",     30,  10)]

let rec pack (knapsack : list<'z>) i capacity =
    if i < 0 || capacity = 0 then ([], 0)
    else 
        let dollName, dollWeight, dollValue = knapsack.[i]
        if dollWeight > capacity then pack knapsack (i-1) capacity
        else
            let knapsackPacked, valPacked = pack knapsack (i-1) (capacity - dollWeight)
            let knapsackNotPacked, valNotPacked = pack knapsack (i-1) capacity
            if (valPacked + dollValue) > valNotPacked then
                let knapsackPacked = dolls.[i] :: knapsackPacked
                (knapsackPacked, (valPacked + dollValue))
            else (knapsackNotPacked, valNotPacked)

let memoize f =
    let memo = Dictionary<_, _>()
    fun x y z ->
        let key = x.ToString() + "_" + y.ToString() + "_" + z.ToString()
        if memo.ContainsKey(key) then memo.[key]
        else let res = f x y
             memo.[key] <- res
             res

let knapsack, value = pack dolls (dolls.Length - 1)  400
printfn "%A" knapsack
printfn "%d" value