Created
May 21, 2012 00:33
-
-
Save ndreynolds/2760047 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
; 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)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment