yowai-01-bnb.jl

# C++ source at geeksforgeeks: https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/

using DataStructures

struct Item
    weight::Float64
    value::Int
end

mutable struct Node
    level::Int
    profit::Int
    bound::Int
    weight::Float64
    
    Node() = new(-1, -1, -1, 0.0)
    Node(a, b, c, d) = new(a, b, c, d)
end


function knapsack(items, W::Int)
    n = length(items)
    
    # @info("$n | $items")
    
    queue = Queue{Node}()
    u = Node(0, 0, -1, 0.0)
    enqueue!(queue, u)
        
    # bounding function
    function bound(node, n)
        # over the capacity
        (node.weight >= W) && return 0.0
        
        # initial bound
        profit_bound = node.profit
        j = node.level + 1
        total_weight = node.weight
        
        # put as much as possible
        while ((j < n) && (total_weight + items[j].weight <= W))
            total_weight += items[j].weight
            profit_bound += items[j].value
            j += 1
        end
        
        if (j < n)
            profit_bound += (W - total_weight) * items[j].value / items[j].weight
        end
        
        # integer profit bound
        ceil(Int, profit_bound)
    end
    
    
    # branch    
    max_profit = 0.0
    while !isempty(queue)
        u = dequeue!(queue)
        (u.level == n - 1) && continue
        vlevel = u.level == 0 ? 1 : u.level + 1
        
        ## take an item
        v = Node(vlevel, u.profit + items[vlevel].value, -1, u.weight + items[vlevel].weight)

        if v.weight <= W && v.profit > max_profit
            max_profit = v.profit
        end
        
        v.bound = bound(v, n)
        if v.bound > max_profit
            enqueue!(queue, v)
        else
            println(">cutting at $v with 1 (to take the item $vlevel)")
        end
        
        ## not take an item
        v = Node(vlevel, u.profit, -1, u.weight)
        v.bound = bound(v, n)
        if v.bound > max_profit
            enqueue!(queue, v)
        else
            println(">cutting at $v with 0 (not to take the item $vlevel)")
        end
    end
    
    max_profit    
end

items = Item[Item(2, 40), Item(3.14, 50), Item(1.98, 100), Item(5, 95), Item(3, 30)]
items_sorted = sort(items, by=item->item.value / item.weight, rev=true)

# display(items_sorted)
res = knapsack(items_sorted, 10)
println("\nmaximum possible profit = $res")

boundバグってるかも？