Class: KnapsackSolver::BranchAndBound

Inherits:
Object
  • Object
show all
Defined in:
lib/knapsack_solver/solving_methods/branch_and_bound.rb

Overview

This class implements methods for solving 0/1 knapsack problem using Branch and Bound method.

Instance Method Summary collapse

Constructor Details

#initialize(instance) ⇒ BranchAndBound

Initializes instance of Brand and Bound 0/1 knapsack problem solver.

Parameters:

  • instance (Instance) —

    0/1 knapsack problem instance



8
9
10
11
 
# File 'lib/knapsack_solver/solving_methods/branch_and_bound.rb', line 8

def initialize(instance)
  @instance = instance
  @config = Array.new(instance.things.size)
end

Instance Method Details

#run ⇒ Hash

Solve the instance of 0/1 knapsack problem.

Returns:

  • (Hash) —

    resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there)



16
17
18
19
 
# File 'lib/knapsack_solver/solving_methods/branch_and_bound.rb', line 16

def run
  solve(0)
  { price: @best_price, config: @best_config }
end