class KnapsackSolver::HeuristicPriceToWeight

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.

Public Class Methods

new(instance) click to toggle source

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

@param instance [Instance] 0/1 knapsack problem instance

# 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

Public Instance Methods

run() click to toggle source

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/heuristic_price_weight.rb, line 21
def run
  solve
  { price: @best_price, config: @best_config }
end

Protected Instance Methods

config_price() click to toggle source

Gets total price of things present in the knapsack.

@return [Integer] total price

# File lib/knapsack_solver/solving_methods/heuristic_price_weight.rb, line 50
def config_price
  @config.each_with_index.reduce(0) do |price, (presence, index)|
    price + presence * @instance.things[index].price
  end
end
config_weight() click to toggle source

Gets total weight of things present in the knapsack.

@return [Integer] total weight

# File lib/knapsack_solver/solving_methods/heuristic_price_weight.rb, line 41
def config_weight
  @config.each_with_index.reduce(0) do |weight, (presence, index)|
    weight + presence * @instance.things[index].weight
  end
end
solve() click to toggle source

Solve the instance of 0/1 knapsack problem.

# File lib/knapsack_solver/solving_methods/heuristic_price_weight.rb, line 29
def solve
  @sorted_things.each do |thing|
    break if (config_weight + thing.weight) > @instance.weight_capacity
    @config[thing.index] = 1
  end
  @best_price = config_price
  @best_config = @config.dup
end