Class: KnapsackSolver::Fptas

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

Overview

This class implements methods for solving 0/1 knapsack problem using Fully Polynomial Time Approximation Scheme.

Instance Method Summary collapse

Constructor Details

#initialize(instance, epsilon) ⇒ Fptas

Initializes 0/1 knapsack FPTAS solver.

Parameters:

  • instance (Instance) —

    Instance of a 0/1 knapsack problem.

  • epsilon (Instances) —

    Maximum allowed relative error of the resulting price.



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

def initialize(instance, epsilon)
  @instance = instance
  @epsilon = epsilon.to_f
  @orig_prices = @instance.things.map(&:price)
end

Instance Method Details

#run ⇒ Hash

Solve the instance of 0/1 knapsack problem using FPTAS.

Returns:

  • (Hash) —

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



20
21
22
23
24
25
 
# File 'lib/knapsack_solver/solving_methods/fptas.rb', line 20

def run
  modify_prices_for_epsilon!
  r = DynamicProgramming.new(@instance).run
  p = get_normal_price_from_fptas(r[:config])
  { price: p, config: r[:config] }
end