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