class KnapsackSolver::Fptas

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

Public Class Methods

new(instance, epsilon) click to toggle source

Initializes 0/1 knapsack FPTAS solver.

@param instance [Instance] Instance of a 0/1 knapsack problem. @param epsilon [Instances] Maximum allowed relative error of the resulting price.

# 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

Public Instance Methods

run() click to toggle source

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

@return [Hash] resulting price and thing configuration (0 = thing is not in the knapsack, 1 = thing is there)

# 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

Protected Instance Methods

get_normal_price_from_fptas(presence) click to toggle source

Computes resulting price using original unmodified prices of things.

@param presenve [Array] configuration variables vector @return [Integer] total price of things in the knapsack

# File lib/knapsack_solver/solving_methods/fptas.rb, line 41
def get_normal_price_from_fptas(presence)
  @instance.things.reduce(0) do |price, t|
    price + ((presence[t.index] != 0 ? @orig_prices[t.index] : 0))
  end
end
modify_prices_for_epsilon!() click to toggle source

Modifies prices of the things according to the supplied epsilon constant to achieve max. allowed relative error.

# File lib/knapsack_solver/solving_methods/fptas.rb, line 31
def modify_prices_for_epsilon!
  m = @instance.things.max_by(&:price).price
  k = (@epsilon * m) / @instance.things.size
  @instance.things.each { |t| t.price = (t.price.to_f / k).floor }
end