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