77 lines
2.8 KiB
Plaintext
77 lines
2.8 KiB
Plaintext
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})
|