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})