### Re: rosettacode 500 milestone passed

I translated the C dynamic programming version:

```sequence 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},
};

sequence {names,weights,points,counts} = columnize(items)

constant n = length(items)

function knapsack(int w)
int v
-- m is the achievable points matrix:
-- Note that Phix uses 1-based indexes, so m[1][1]
--  actually holds points for 0 items of weight 0,
--  and m[n+1][w+1] is for n items at weight w.
seq m = repeat(repeat(0,w+1),n+1)
for i=1 to n do
for j=1 to w+1 do       -- (0 to w really)
m[i+1][j] = m[i][j]
for k=1 to counts[i] do
if k*weights[i]>j-1 then
exit
end if
v = m[i][j-k*weights[i]]+k*points[i]
if v>m[i+1][j] then
m[i+1][j] = v
end if
end for
end for
end for
seq s = repeat(0,n)
int j = w+1                 -- (w -> 0 really)
for i=n+1 to 2 by -1 do     -- (n to 1 really)
v = m[i][j]
int k = 0
while v!=m[i-1][j]+k*points[i-1] do
s[i-1] += 1
j -= weights[i-1]
k += 1
end while
end for
return s
end function

int tc = 0, tw = 0, tv = 0
seq s = knapsack(400)
for i=1 to n do
int si = s[i]
if si then
printf(1,"%-22s %5d %5d %5d\n", {names[i], si, si*weights[i], si*points[i]})
tc += si
tw += si*weights[i]
tv += si*points[i]
end if
end for
printf(1,"%-22s %5d %5d %5d\n", {"count, weight, points:", tc, tw, tv})
```

Simple and elegant, yet quite difficult to get your head around - there are some youtube vids (search for knapsack problem) that might help.

Pete

Not signed in.