include xpllib;         \for Print and IntSize
def N = 22;             \number of Items
int  Items, S(N);
def \Items\ Name, Weight, Value, Count;

proc Knapsack(W);
int  W;
int  I, J, K, V, MM, M;
[MM:= Reserve((N+1)*(W+1)*IntSize);
M:= Reserve((N+1)*IntSize);
M(0):= MM;
for I:= 1 to N do
    [M(I):= @MM(I*(W+1));
    for J:= 0 to W do
        [M(I, J):= M(I-1, J);
        for K:= 1 to Items(I-1, Count) do
            [if K*Items(I-1, Weight) <= J then
                [V:= M(I-1, J-K*Items(I-1, Weight)) + K*Items(I-1, Value);
                if V > M(I, J) then M(I, J):= V;
                ];
            ];
        ];
    ];
I:= N;  J:= W;
while I > 0 do
        [V:= M(I, J);
        K:= 0;
        while V # M(I-1, J) + K*Items(I-1, Value) do
                [S(I-1):= S(I-1) + 1;
                J:= J - Items(I-1, Weight);
                K:= K+1;
                ];
        I:= I-1;
        ];
];

int I, TC, TW, TV;
[Items:= [
    ["map                   ",   9,   150,   1],
    ["compass               ",  13,    35,   1],
    ["water                 ", 153,   200,   2],
    ["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],
    ["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] ];
TC:= 0;  TW:= 0;  TV:= 0;
Knapsack(400);          \maximum weight = 400 decigrams = 4.0 killograms
for I:= 0 to N-1 do
    [if S(I) then
        [Print("%s %5d %5d %5d\n",
             Items(I, Name), S(I), S(I)*Items(I, Weight), S(I)*Items(I, Value));
        TC:= TC + S(I);                         \accumulate totals
        TW:= TW + S(I)*Items(I, Weight);
        TV:= TV + S(I)*Items(I, Value);
        ];
    ];
Print("%s %5d %5d %5d\n", "count, weight, value: ", TC, TW, TV);
]