Lab 10

-- "Global" variables
local W = 10
local p = {21, 30, 20, 18}
local w = {3, 5, 4, 6}
local n = #p

local class = require "clasp"

local Node = class {
    isNode = true,

    init = function(self, level, weight, profit)
        self.level = level or 0
        self.weight = weight or 0
        self.profit = profit or 0
        self.bound = bound(self)
    end,
}

local PriorityQueue = class {
    init = function(self)
        self.items = {}
    end,
    push = function(self, node)
        if not node.isNode then return end

        table.insert(self.items, node)

        -- Sorts ascending
        table.sort(self.items, function(a, b)
            return a.weight < b.weight
        end)

    end,
    pop = function(self)
        local node = self.items[#self.items]
        table.remove(self.items, #self.items)
        return node
    end,

    isEmpty = function(self)
        return #self.items == 0
    end,
}

function bound(node)
    if node.weight >= W then return 0 end

    local result = node.profit
    local j = node.level + 1
    local totalWeight = node.weight

    while j <= n and totalWeight + w[j] <= W do
        totalWeight = totalWeight + w[j]
        result = result + p[j]
        j = j + 1
    end

    local k = j
    if k <= n then
        result = result + (W - totalWeight) * (p[k]/w[k])
    end

    return result
end

function knapsack3()

    local PQ = PriorityQueue()
    local v = Node()
    print(v.bound)
    local maxProfit = 0

    PQ:push(v)

    while not PQ:isEmpty() do
        local v = PQ:pop()
        if v.bound > maxProfit then

            local level = v.level + 1
            local weight = v.weight + w[level]
            local profit = v.profit + p[level]

            if weight <= W and profit > maxProfit then
                maxProfit = profit
            end

            local newNode = Node(level, weight, profit)
            if newNode.bound > maxProfit then
                PQ:push(newNode)
            end

            local newerNode = Node(level, v.weight, v.profit)
            if newerNode.bound > maxProfit then
                PQ:push(newerNode)
            end
        end

    end

    return maxProfit
end

local maxProfit = knapsack3()
print(maxProfit)