76 lines
2.7 KiB
Text
76 lines
2.7 KiB
Text
link printf
|
|
|
|
global wants # items wanted for knapsack
|
|
|
|
procedure main(A) # kanpsack 0-1
|
|
if !A == ("--trace"|"-t") then &trace := -1 # trace everything (debug)
|
|
if !A == ("--memoize"|"-m") then m :=: Memo_m # hook (swap) procedure
|
|
|
|
printf("Knapsack-0-1: with maximum weight allowed=%d.\n",maxw := 400)
|
|
showwanted(wants := get_wants())
|
|
showcontents(bag := m(*wants,maxw))
|
|
printf("Performance: time=%d ms collections=%d\n",&time,&collections)
|
|
end
|
|
|
|
record packing(items,weight,value)
|
|
|
|
procedure Memo_m(i,w) #: Hook procedure to memoize the knapsack
|
|
static memoT
|
|
initial memoT := table()
|
|
return \memoT[k := i||","||w] | ( memoT[k] := Memo_m(i,w) )
|
|
end
|
|
|
|
procedure m(i,w) #: Solve the Knapsack 0-1 as per Wikipedia
|
|
static nil
|
|
initial nil := packing([],0,0)
|
|
if 0 = (i | w) then
|
|
return nil
|
|
else if wants[i].weight > w then
|
|
return m(i-1, w)
|
|
else {
|
|
x0 := m(i-1,w)
|
|
x1 := m(i-1,w-wants[i].weight)
|
|
if ( x1.value + wants[i].value) > x0.value then
|
|
return packing(x1.items ||| wants[i].items,
|
|
x1.weight + wants[i].weight,
|
|
x1.value + wants[i].value)
|
|
else
|
|
return x0
|
|
}
|
|
end
|
|
|
|
procedure showwanted(wants) #: show the list of wanted items
|
|
every (tw := 0) +:= (!wants).weight
|
|
printf("Packing list has total weight=%d and includes %d items [",tw,*wants)
|
|
every printf(" %s",!(!wants).items|"]\n")
|
|
end
|
|
|
|
procedure showcontents(bag) #: show the list of the packed bag
|
|
printf("The bag weighs=%d holding %d items [",bag.weight,*bag.items)
|
|
every printf(" %s",!bag.items|"]\n")
|
|
end
|
|
|
|
procedure get_wants() #: setup list of wanted items
|
|
return [ packing(["map"], 9, 150),
|
|
packing(["compass"], 13, 35),
|
|
packing(["water"], 153, 200),
|
|
packing(["sandwich"], 50, 160),
|
|
packing(["glucose"], 15, 60),
|
|
packing(["tin"], 68, 45),
|
|
packing(["banana"], 27, 60),
|
|
packing(["apple"], 39, 40),
|
|
packing(["cheese"], 23, 30),
|
|
packing(["beer"], 52, 10),
|
|
packing(["suntan cream"], 11, 70),
|
|
packing(["camera"], 32, 30),
|
|
packing(["T-shirt"], 24, 15),
|
|
packing(["trousers"], 48, 10),
|
|
packing(["umbrella"], 73, 40),
|
|
packing(["waterproof trousers"], 42, 70),
|
|
packing(["waterproof overclothes"], 43, 75),
|
|
packing(["note-case"], 22, 80),
|
|
packing(["sunglasses"], 7, 20),
|
|
packing(["towel"], 18, 12),
|
|
packing(["socks"], 4, 50),
|
|
packing(["book"], 30, 10) ]
|
|
end
|