85 lines
2.5 KiB
Text
85 lines
2.5 KiB
Text
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)
|