Class: KnapsackSolver::HeuristicPriceToWeight

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

Overview

This class implements methods for solving 0/1 knapsack problem using simple heuristic by price to weight ratio. Things with the best price to weight ratio are selected first.

Instance Method Summary collapse

Constructor Details

#initialize(instance) ⇒ HeuristicPriceToWeight

Initializes instance of 0/1 knapsack problem solver using simple heuristic by price to weight ratio.

Parameters:

  • instance (Instance) —

    0/1 knapsack problem instance



10
11
12
13
14
15
16
 
# File 'lib/knapsack_solver/solving_methods/heuristic_price_weight.rb', line 10

def initialize(instance)
  @instance = instance
  @config = Array.new(instance.things.size) { 0 }
  @sorted_things = instance.things.sort do |a, b|
    (b.price.to_f / b.weight) <=> (a.price.to_f / a.weight)
  end
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)



21
22
23
24
 
# File 'lib/knapsack_solver/solving_methods/heuristic_price_weight.rb', line 21

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