68 lines
1.9 KiB
Text
68 lines
1.9 KiB
Text
require "table2"
|
|
local fmt = require "fmt"
|
|
|
|
class item
|
|
function __construct(public name, public value, public weight, public volume)
|
|
end
|
|
end
|
|
|
|
local items = {
|
|
new item("panacea", 3000, 0.3, 0.025),
|
|
new item("ichor", 1800, 0.2, 0.015),
|
|
new item("gold", 2500, 2, 0.002)
|
|
}
|
|
|
|
local n = #items
|
|
local count = table.rep(n, 0)
|
|
local best = table.rep(n, 0)
|
|
local best_value = 0
|
|
local max_weight = 25
|
|
local max_volume = 0.25
|
|
|
|
local function knapsack(i, value, weight, volume)
|
|
if i == n + 1 then
|
|
if value > best_value then
|
|
best_value = value
|
|
for j = 1, n do best[j] = count[j] end
|
|
end
|
|
return
|
|
end
|
|
local m1 = weight // items[i].weight
|
|
local m2 = volume // items[i].volume
|
|
count[i] = math.min(m1, m2)
|
|
while count[i] >= 0 do
|
|
knapsack(
|
|
i + 1,
|
|
value + count[i] * items[i].value,
|
|
weight - count[i] * items[i].weight,
|
|
volume - count[i] * items[i].volume
|
|
)
|
|
count[i] -= 1
|
|
end
|
|
end
|
|
|
|
knapsack(1, 0, max_weight, max_volume)
|
|
print("Item Chosen Number Value Weight Volume")
|
|
print("----------- ------ ----- ------ ------")
|
|
local item_count = 0
|
|
local sum_number = 0
|
|
local sum_weight = 0
|
|
local sum_volume = 0
|
|
for i = 1, n do
|
|
if best[i] != 0 then
|
|
item_count += 1
|
|
local name = items[i].name
|
|
local number = best[i]
|
|
local value = items[i].value * number
|
|
local weight = items[i].weight * number
|
|
local volume = items[i].volume * number
|
|
sum_number += number
|
|
sum_weight += weight
|
|
sum_volume += volume
|
|
local f = "%-11s %2d %5.0f %4.1f %4.2f"
|
|
fmt.print(f, name, number, value, weight, volume)
|
|
end
|
|
end
|
|
print("----------- ------ ----- ------ ------")
|
|
local f = "%d items %2d %5.0f %4.1f %4.2f"
|
|
fmt.print(f, item_count, sum_number, best_value, sum_weight, sum_volume)
|