Class: KnapsackSolver::DynamicProgramming

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

Overview

This class implements methods for solving 0/1 knapsack problem using dynamic programming with decomposition by price.

Instance Method Summary collapse

Constructor Details

#initialize(instance) ⇒ DynamicProgramming

Initializes instance of 0/1 knapsack problem solver based on dynamic programming with decomposition by price.

Parameters:

  • instance (Instance) —

    0/1 knapsack problem instance



9
10
11
12
 
# File 'lib/knapsack_solver/solving_methods/dynamic_programming.rb', line 9

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)



17
18
19
20
 
# File 'lib/knapsack_solver/solving_methods/dynamic_programming.rb', line 17

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