65 lines
2.3 KiB
Plaintext
65 lines
2.3 KiB
Plaintext
atom t0 = time()
|
|
|
|
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}}
|
|
|
|
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
|
|
integer {?,witem,pitem,imax} = goodies[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
|
|
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
|
|
printf(1,"Value %d, weight %g [%3.2fs]\n",{points,weight,time()-t0})
|