142 lines
5.0 KiB
Plaintext
142 lines
5.0 KiB
Plaintext
--
|
|
-- demo\rosetta\knapsackB.exw
|
|
-- ==========================
|
|
--
|
|
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)
|
|
if actual_weight>weight then ?9/0 end if
|
|
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
|
|
for i=1 to length(range_cache[at]) do
|
|
sequence rcati = range_cache[at][i]
|
|
if weight=rcati[ACTW] then
|
|
if rcati[PTS..SOLN]!={points,actual_weight,soln} then ?9/0 end if
|
|
return
|
|
elsif weight<rcati[ACTW] then
|
|
-- (we cannot extend an existing range down, since it starts at
|
|
-- the actual weight, that must also be the minimum weight...)
|
|
if soln=rcati[SOLN] then ?9/0 end if
|
|
-- insert a new range
|
|
range_cache[at][i..i-1] = {{weight,points,actual_weight,soln}}
|
|
cache_entries += 1
|
|
return
|
|
elsif soln=rcati[SOLN] then
|
|
if rcati[PTS..SOLN]!={points,actual_weight,soln} then ?9/0 end if
|
|
if weight>rcati[HI] then -- extend existing range up
|
|
rcati = {}
|
|
range_cache[at][i][HI] = weight
|
|
end if
|
|
return
|
|
elsif weight<=rcati[HI] then
|
|
?9/0 -- duplicate solution?? (or discard as below)
|
|
-- return -- (discard)
|
|
end if
|
|
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
|
|
|
|
constant 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 = 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
|
|
for i=1 to length(goodies) do
|
|
integer c = res[3][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
|
|
if points!=res[1] then ?9/0 end if -- sanity check
|
|
if weight!=res[2] then ?9/0 end if -- 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})
|