73 lines
2.1 KiB
Text
73 lines
2.1 KiB
Text
knapsack[values, weights, capacity] :=
|
|
{
|
|
n = length[values]
|
|
|
|
if length[weights] != n
|
|
{
|
|
println["knapsack: length of values does not equal length of weights."]
|
|
return undef
|
|
}
|
|
|
|
V = new array[[n+1, capacity+1], 0]
|
|
keep = new array[[n+1, capacity+1], false]
|
|
|
|
for i = 1 to n
|
|
{
|
|
for w = 0 to capacity
|
|
{
|
|
if weights@(i-1) <= w and (values@(i-1) + V@(i-1)@(w - weights@(i-1)) > V@(i-1)@w)
|
|
{
|
|
V@i@w = values@(i-1) + V@(i-1)@(w-weights@(i-1))
|
|
keep@i@w = true
|
|
} else
|
|
{
|
|
V@i@w = V@(i-1)@w
|
|
keep@i@w = false
|
|
}
|
|
}
|
|
}
|
|
|
|
included = new array
|
|
K = capacity
|
|
for i = n to 1 step -1
|
|
if keep@i@K == true
|
|
{
|
|
included.push[ [i-1, values@(i-1), weights@(i-1)] ]
|
|
K = K - weights@(i-1)
|
|
}
|
|
|
|
return concat[V@n@capacity, included.transpose[]]
|
|
}
|
|
|
|
i= [["map", 9, 150],
|
|
["compass", 13, 35],
|
|
["water", 153, 200],
|
|
["sandwich", 50, 160],
|
|
["glucose", 15, 60],
|
|
["tin", 68, 45],
|
|
["banana", 27, 60],
|
|
["apple", 39, 40],
|
|
["cheese", 23, 30],
|
|
["beer", 52, 10],
|
|
["suntan cream", 11, 70],
|
|
["camera", 32, 30],
|
|
["T-shirt", 24, 15],
|
|
["trousers", 48, 10],
|
|
["umbrella", 73, 40],
|
|
["waterproof trousers", 42, 70],
|
|
["waterproof overclothes", 43, 75],
|
|
["note-case", 22, 80],
|
|
["sunglasses", 7, 20],
|
|
["towel", 18, 12],
|
|
["socks", 4, 50],
|
|
["book", 30, 10]]
|
|
|
|
[maxval, indices, values, weights] = knapsack[i.getColumn[2], i.getColumn[1], 400]
|
|
println["Items:"]
|
|
|
|
for ind = sort[indices]
|
|
println[" " +i@ind@0]
|
|
|
|
println[]
|
|
println["Total weight: " + sum[weights]]
|
|
println["Total value: $maxval"]
|