(phixonline)-->
-- demo\rosetta\knapsackB.exw
with javascript_semantics
atom t0 = time()
enum HI,PTS,ACTW,SOLN
sequence range_cache = {}
integer cache_entries = 0
procedure add_range(integer at, atom weight, atom actual_weight, atom points, sequence soln)
assert(actual_weight<=weight)
for i=length(range_cache)+1 to at do -- (while too small do)
if i=at then
range_cache = append(range_cache,{{weight,points,actual_weight,soln}})
cache_entries += 1
return
end if
range_cache = append(range_cache,{})
end for
integer lastHI = -1
for i=1 to length(range_cache[at]) do
sequence rcati = range_cache[at][i]
if weight=rcati[ACTW] then
assert(rcati[PTS..SOLN]=={points,actual_weight,soln})
return
elsif weight<rcati[ACTW] then
-- (we cannot extend an existing range down...)
assert(soln!=rcati[SOLN])
-- insert a new range
range_cache[at][i..i-1] = {{weight,points,actual_weight,soln}}
cache_entries += 1
return
elsif soln=rcati[SOLN] then
assert(rcati[PTS..SOLN]=={points,actual_weight,soln})
if weight>rcati[HI] then -- extend existing range up
rcati = {}
range_cache[at][i][HI] = weight
end if
return
elsif weight<=rcati[HI] then
crash("duplicate solution??") -- (or discard as below)
-- return -- (discard)
end if
assert(rcati[ACTW]>lastHI)
lastHI = rcati[HI]
end for
range_cache[at] = append(range_cache[at],{weight,points,actual_weight,soln})
cache_entries += 1
end procedure
function in_range(integer at, atom weight)
if at<=length(range_cache) then
for i=1 to length(range_cache[at]) do
sequence rcati = range_cache[at][i]
if weight<=rcati[HI] then
if weight>=rcati[ACTW] then
return rcati[PTS..SOLN] -- {pts,act_weight,soln}
end if
exit
end if
end for
end if
return {} -- (no suitable cache entry found)
end function
sequence goodies = ({
-- item weight value pieces
{"map", 9, 150, 1},
{"compass", 13, 35, 1},
{"sandwich", 50, 60, 2},
{"glucose", 15, 60, 2},
{"tin", 68, 45, 3},
{"banana", 27, 60, 3},
{"apple", 39, 40, 3},
{"cheese", 23, 30, 1},
{"beer", 52, 10, 3},
{"suntan cream", 11, 70, 1},
{"water", 153, 200, 2},
{"camera", 32, 30, 1},
{"T-shirt", 24, 15, 2},
{"trousers", 48, 10, 2},
{"umbrella", 73, 40, 1},
{"waterproof trousers", 42, 70, 1},
{"waterproof overclothes", 43, 75, 1},
{"note-case", 22, 80, 1},
{"sunglasses", 7, 20, 1},
{"towel", 18, 12, 2},
{"socks", 4, 50, 1},
{"book", 30, 10, 2}})
integer cache_hits = 0
integer cache_misses = 0
function knapsack(integer max_weight, integer at)
integer best_points = 0, points
sequence best_choices = {}, choices
atom act_weight = 0, sub_weight
if at>=1 then
sequence soln = in_range(at,max_weight)
if length(soln) then
cache_hits += 1
return soln
end if
cache_misses += 1
integer {?,witem,pitem,imax} = goodies[at]
best_choices = repeat(0,at)
for i=0 to imax do
integer wlim = max_weight-i*witem
if wlim<0 then exit end if
{points,sub_weight,choices} = knapsack(wlim, at-1)
points += i*pitem
if points>best_points then
best_points = points
best_choices = deep_copy(choices)&i
act_weight = sub_weight+i*witem
end if
end for
add_range(at,max_weight,act_weight,best_points,best_choices)
end if
return {best_points, act_weight, best_choices}
end function
sequence res = knapsack(400, length(goodies)) -- {points,act_weight,choices}
atom weight = 0, witem
atom points = 0, pitem
string idesc
sequence choices = res[3]
for i=1 to length(goodies) do
integer c = choices[i]
if c then
{idesc,witem,pitem} = goodies[i]
printf(1,"%d %s\n",{c,idesc})
weight += c*witem
points += c*pitem
end if
end for
assert({points,weight}==res[1..2]) -- sanity check
printf(1,"Value %d, weight %g [%3.2fs]:\n",{points,weight,time()-t0})
printf(1,"cache_entries:%d, hits:%d, misses:%d\n",{cache_entries,cache_hits,cache_misses})