Knapsack problem

[Lucas]

and:

procedure show(sequence cost, sequence mat, integer j)
integer c, len
sequence temp
len = length(cost)
printf(1, "%d=", j - 1)
while j > 1 do
temp = mat[j]
for i = 1 to len do
if temp[i] then
c = cost[i]
printf(1,"+%d", c)
j -= c
exit
end if
end for
end while
puts(1, "\n")
end procedure

procedure showall(sequence cost, sequence mat, integer j)
integer c, len, k, i, m, f, h
sequence temp, v
len = length(cost)
v = repeat(0, j)
v[j] = len + 1
k = j
i = 1
while 1 do
temp = mat[k]
f = 1
while i < v[k] do
if temp[i] then
k -= cost[i]
v[k] = i
if k = 1 then
printf(1, "%d=", j - 1)
m = 1
h = i
while m < j do
c = cost[h]
printf(1, "+%d", c)
m += c
h = v[m]
end while
puts(1, "\n")
exit
end if
f = 0
i = 1
exit
end if
i += 1
end while
if i > len then
exit
end if
if f then
k += cost[i]
i += 1
end if
end while
puts(1, "\n")
end procedure

procedure knapsack(sequence cost)
sequence sol, mat
integer tot, len, c, v
object ct
len = length(cost)
-- Check data and compute maximum possible goal value
-- (plus 1 because the EU index origin is 1)
tot = 1
for i = 1 to len do
ct = cost[i]
if integer(ct) and ct > 0 then
tot += ct
else
puts(1, "Only positive integers allowed")
exit
end if
end for
sol = repeat(0, tot)
mat = repeat(repeat(0, len), tot)
-- mat[x][y]=1 means that total x-1 may contain cost[y]
for i = 1 to len do
c = cost[i]
for j = tot to 1 by -1 do -- down to avoid spurious repetitions
if sol[j] then
v = j + c
if v <= tot then
sol[v] = 1
mat[v][i] = 1
end if
end if
end for
sol[c + 1] = 1
mat[c + 1][i] = 1
end for
for j = 1 to tot do
if sol[j] then -- only for sum strictly equal to the goal
show(cost, mat, j)
end if
end for
puts(1, "\n")
end procedure

-- Sample data.

knapsack({2, 3, 5, 7, 10})

knapsack({343,785,351,221,248,177,143,217,154,166,235,96,362,177,232,146,351,290,346,178,191})