class KnapsackSolver::BranchAndBound
This class implements methods for solving 0/1 knapsack problem using Branch and Bound method.
Public Class Methods
Initializes instance of Brand and Bound 0/1 knapsack problem solver.
@param instance [Instance] 0/1 knapsack problem instance
# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 8 def initialize(instance) @instance = instance @config = Array.new(instance.things.size) end
Public Instance Methods
Solve the instance of 0/1 knapsack problem.
@return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there)
# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 16 def run solve(0) { price: @best_price, config: @best_config } end
Protected Instance Methods
Gets price of set of things. The set is subset of the things ordered by their index.
@param start_index [Integer] index of the first thing included in the set @param end_index [Integer] index of the last thing included in the set @return [Integer] price of the things
# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 91 def config_price(start_index, end_index) price = 0 @config[start_index..end_index].each_with_index do |presence, index| price += presence * @instance.things[index].price end price end
Gets weight of set of things. The set is subset of the things ordered by their index.
@param start_index [Integer] index of the first thing included in the set @param end_index [Integer] index of the last thing included in the set @return [Integer] weight of the things
# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 77 def config_weight(start_index, end_index) weight = 0 @config[start_index..end_index].each_with_index do |presence, index| weight += presence * @instance.things[index].weight end weight end
Gets sum of prices of things for which their presence in the knapsack was not decided yet.
@param from_index [Integer] index of the first undecided thing @return [Integer] price of the remaining things
# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 104 def get_price_of_remaining_things(from_index) price = 0 to_index = @instance.things.size - 1 @instance.things[from_index..to_index].each { |t| price += t.price } price end
Solve the problem starting at specified thing.
@param index [Integer] index of thing which will be decided (put in or out from the knapsack) the next
# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 26 def solve(index) @config[index] = 0 solve(index + 1) unless stop(index) @config[index] = 1 solve(index + 1) unless stop(index) end
Determine if solving of current branch should continue.
@param index [Integer] index of the last decided thing so far @return [true, false] weather to continue with solving current branch.
# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 37 def stop(index) # Update of the best price so far weight = config_weight(0, index) price = config_price(0, index) update_best_price(price, weight, index) # No more things to put into the knapsack return true if index >= (@instance.things.size - 1) # The knapsack is overloaded, do not continue this branch return true if weight > @instance.weight_capacity if instance_variable_defined?('@best_price') && ((price + get_price_of_remaining_things(index + 1)) <= @best_price) # Adding all the ramining things does not produce better price return true end false end
Update the best price achieved so far.
@param price [Integer] price of the current configuration @param weight [Integer] weight of the current configuration @param index [Integer] index of the next thing presence of which will be decided
# File lib/knapsack_solver/solving_methods/branch_and_bound.rb, line 59 def update_best_price(price, weight, index) if !instance_variable_defined?('@best_price') || ((weight <= @instance.weight_capacity) && (price > @best_price)) @best_price = price valid_len = index + 1 remaining = @config.size - index - 1 # All undecided things will not be put into the knapsack @best_config = @config.slice(0, valid_len).fill(0, valid_len, remaining) @best_config_index = index end end