Initial commit

1 files changed, 47 insertions, 0 deletions

diff --git a/lib/knapsack_solver/solving_methods/fptas.rb b/lib/knapsack_solver/solving_methods/fptas.rb
new file mode 100644
index 0000000..55ee52f
--- /dev/null
+++ b/lib/knapsack_solver/solving_methods/fptas.rb
@@ -0,0 +1,47 @@
+require 'knapsack_solver/solving_methods/dynamic_programming'
+
+module KnapsackSolver
+  # This class implements methods for solving 0/1 knapsack problem using Fully
+  # Polynomial Time Approximation Scheme.
+  class Fptas
+    # 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.
+    def initialize(instance, epsilon)
+      @instance = instance
+      @epsilon = epsilon.to_f
+      @orig_prices = @instance.things.map(&:price)
+    end
+
+    # 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)
+    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
+
+    # Modifies prices of the things according to the supplied epsilon constant
+    # to achieve max. allowed relative error.
+    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
+
+    # Computes resulting price using original unmodified prices of things.
+    #
+    # @param presenve [Array] configuration variables vector
+    # @return [Integer] total price of things in the knapsack
+    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
+  end
+end