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)