require "table2"
local fmt = require "fmt"

class item
    function __construct(public name, public weight, public value, public count)
    end
end

local items = {
    new item("map", 9, 150, 1),
    new item("compass", 13, 35, 1),
    new item("water", 153, 200, 2),
    new item("sandwich", 50, 60, 2),
    new item("glucose", 15, 60, 2),
    new item("tin", 68, 45, 3),
    new item("banana", 27, 60, 3),
    new item("apple", 39, 40, 3),
    new item("cheese", 23, 30, 1),
    new item("beer", 52, 10, 3),
    new item("suntan cream", 11, 70, 1),
    new item("camera", 32, 30, 1),
    new item("T-shirt", 24, 15, 2),
    new item("trousers", 48, 10, 2),
    new item("umbrella", 73, 40, 1),
    new item("waterproof trousers", 42, 70, 1),
    new item("waterproof overclothes", 43, 75, 1),
    new item("note-case", 22, 80, 1),
    new item("sunglasses", 7, 20, 1),
    new item("towel", 18, 12, 2),
    new item("socks", 4, 50, 1),
    new item("book", 30, 10, 2)
}

local n = #items
local max_weight = 400

local function knapsack(w)
    local m = table.create(n + 1)
    for i = 0, n do m[i + 1] = table.rep(w + 1, 0) end
    for i = 1, n do
        for j = 0, w do
            m[i + 1][j + 1] = m[i][j + 1]
            for k = 1, items[i].count do
                if k * items[i].weight > j then break end
                local v = m[i][j - k * items[i].weight + 1] + k * items[i].value
                if v > m[i + 1][j + 1] then m[i + 1][j + 1] = v end
            end
        end
    end
    local s = table.rep(n, 0)
    local j = w
    for i = n, 1, -1 do
        local v = m[i + 1][j + 1]
        local k = 0
        while v != m[i][j + 1] + k * items[i].value do
            s[i] += 1
            j -= items[i].weight
            k += 1
        end
    end
    return s
end

local s = knapsack(max_weight)
print("Item Chosen             Weight Value  Number")
print("---------------------   ------ -----  ------")
local item_count = 0
local sum_weight = 0
local sum_value  = 0
local sum_number = 0
for i = 1, n do
       if s[i] != 0 then
           item_count  += 1
           local name   = items[i].name
           local number = s[i]
           local weight = items[i].weight * number
           local value  = items[i].value  * number
           sum_number  += number
           sum_weight  += weight
           sum_value   += value
           fmt.print("%-22s    %3d   %4d    %2d", name, weight, value, number)
       end
end
print("---------------------   ------ -----  ------")
fmt.print("Items chosen %d           %3d   %4d    %2d", item_count, sum_weight, sum_value, sum_number)