68 lines
2.3 KiB
Text
68 lines
2.3 KiB
Text
integer terminate=0
|
|
|
|
integer attempts = 0
|
|
function knapsack(sequence res, goodies, atom points, weight, at=1, sequence chosen={})
|
|
atom {witem,pitem} = goodies[at][2]
|
|
integer n = (witem<=weight)
|
|
chosen &= n
|
|
points += n*pitem -- increase value
|
|
weight -= n*witem -- decrease weight left
|
|
if at=length(goodies) then
|
|
attempts += 1
|
|
if length(res)=0
|
|
or res<{points,weight} then
|
|
res = {points,weight,chosen}
|
|
end if
|
|
terminate = (n=1)
|
|
else
|
|
while n>=0 and not terminate do
|
|
res = knapsack(res,goodies,points,weight,at+1,chosen)
|
|
n -= 1
|
|
chosen[$] = n
|
|
points -= pitem
|
|
weight += witem
|
|
end while
|
|
end if
|
|
return res
|
|
end function
|
|
|
|
function byweightedvalue(object a, b)
|
|
-- sort by weight/value
|
|
return compare(a[2][1]/a[2][2],b[2][1]/b[2][2])
|
|
-- nb other sort orders break the optimisation
|
|
end function
|
|
|
|
constant goodies = custom_sort(routine_id("byweightedvalue"),{
|
|
-- item weight value
|
|
{"map", {9, 150}},
|
|
{"compass", {13, 35 }},
|
|
{"water", {153, 200}},
|
|
{"sandwich", {50, 160}},
|
|
{"glucose", {15, 60 }},
|
|
{"tin", {68, 45 }},
|
|
{"banana", {27, 60 }},
|
|
{"apple", {39, 40 }},
|
|
{"cheese", {23, 30 }},
|
|
{"beer", {52, 10 }},
|
|
{"suntan cream", {11, 70 }},
|
|
{"camera", {32, 30 }},
|
|
{"T-shirt", {24, 15 }},
|
|
{"trousers", {48, 10 }},
|
|
{"umbrella", {73, 40 }},
|
|
{"waterproof trousers", {42, 70 }},
|
|
{"waterproof overclothes", {43, 75 }},
|
|
{"note-case", {22, 80 }},
|
|
{"sunglasses", {7, 20 }},
|
|
{"towel", {18, 12 }},
|
|
{"socks", {4, 50 }},
|
|
{"book", {30, 10 }}})
|
|
|
|
atom t0 = time()
|
|
object {points,weight,counts} = knapsack({},goodies,0,400)
|
|
printf(1,"Value %d, weight %g [%d attempts, %3.2fs]:\n",{points,400-weight,attempts,time()-t0})
|
|
for i=1 to length(counts) do
|
|
integer c = counts[i]
|
|
if c then
|
|
printf(1,"%s\n",{goodies[i][1]})
|
|
end if
|
|
end for
|