51 lines
1.3 KiB
Text
51 lines
1.3 KiB
Text
local fmt = require "fmt"
|
|
|
|
local wants = {
|
|
{"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}
|
|
}
|
|
|
|
local function m(i, w)
|
|
if i < 1 or w == 0 then return {}, 0, 0 end
|
|
if wants[i][2] > w then return m(i - 1, w) end
|
|
local i0, w0, v0 = m(i - 1, w)
|
|
local i1, w1, v1 = m(i - 1, w - wants[i][2])
|
|
v1 += wants[i][3]
|
|
if v1 > v0 then
|
|
i1:insert(wants[i])
|
|
return i1, w1 + wants[i][2], v1
|
|
end
|
|
return i0, w0, v0
|
|
end
|
|
|
|
local max_wt = 400
|
|
local items, tw, tv = m(#wants, max_wt)
|
|
print($"Max weight: {max_wt}\n")
|
|
print("Item Weight Value")
|
|
print("------------------------------------")
|
|
for i = 1, #items do
|
|
local [item, w, v] = items[i]
|
|
fmt.print("%-22s %3d %4s", item, w, v)
|
|
end
|
|
print(" --- ----")
|
|
fmt.print("totals %3d %4d", tw, tv)
|