Initial commit

4 files changed, 330 insertions, 0 deletions

diff --git a/lib/knapsack_solver/solving_methods/branch_and_bound.rb b/lib/knapsack_solver/solving_methods/branch_and_bound.rb
new file mode 100644
index 0000000..64d7092
--- /dev/null
+++ b/lib/knapsack_solver/solving_methods/branch_and_bound.rb
@@ -0,0 +1,111 @@
+module KnapsackSolver
+  # This class implements methods for solving 0/1 knapsack problem using
+  # Branch and Bound method.
+  class BranchAndBound
+    # Initializes instance of Brand and Bound 0/1 knapsack problem solver.
+    #
+    # @param instance [Instance] 0/1 knapsack problem instance
+    def initialize(instance)
+      @instance = instance
+      @config = Array.new(instance.things.size)
+    end
+
+    # 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)
+    def run
+      solve(0)
+      { price: @best_price, config: @best_config }
+    end
+
+    protected
+
+    # Solve the problem starting at specified thing.
+    #
+    # @param index [Integer] index of thing which will be decided (put in or out from the knapsack) the next
+    def solve(index)
+      @config[index] = 0
+      solve(index + 1) unless stop(index)
+      @config[index] = 1
+      solve(index + 1) unless stop(index)
+    end
+
+    # Determine if solving of current branch should continue.
+    #
+    # @param index [Integer] index of the last decided thing so far
+    # @return [true, false] weather to continue with solving current branch.
+    def stop(index)
+      # Update of the best price so far
+      weight = config_weight(0, index)
+      price = config_price(0, index)
+      update_best_price(price, weight, index)
+      # No more things to put into the knapsack
+      return true if index >= (@instance.things.size - 1)
+      # The knapsack is overloaded, do not continue this branch
+      return true if weight > @instance.weight_capacity
+      if instance_variable_defined?('@best_price') &&
+         ((price + get_price_of_remaining_things(index + 1)) <= @best_price)
+        # Adding all the ramining things does not produce better price
+        return true
+      end
+      false
+    end
+
+    # Update the best price achieved so far.
+    #
+    # @param price [Integer] price of the current configuration
+    # @param weight [Integer] weight of the current configuration
+    # @param index [Integer] index of the next thing presence of which will be decided
+    def update_best_price(price, weight, index)
+      if !instance_variable_defined?('@best_price') ||
+         ((weight <= @instance.weight_capacity) && (price > @best_price))
+        @best_price = price
+        valid_len = index + 1
+        remaining = @config.size - index - 1
+        # All undecided things will not be put into the knapsack
+        @best_config = @config.slice(0, valid_len).fill(0, valid_len, remaining)
+        @best_config_index = index
+      end
+    end
+
+    # Gets weight of set of things. The set is subset of the things ordered by
+    # their index.
+    #
+    # @param start_index [Integer] index of the first thing included in the set
+    # @param end_index [Integer] index of the last thing included in the set
+    # @return [Integer] weight of the things
+    def config_weight(start_index, end_index)
+      weight = 0
+      @config[start_index..end_index].each_with_index do |presence, index|
+        weight += presence * @instance.things[index].weight
+      end
+      weight
+    end
+
+    # Gets price of set of things. The set is subset of the things ordered by
+    # their index.
+    #
+    # @param start_index [Integer] index of the first thing included in the set
+    # @param end_index [Integer] index of the last thing included in the set
+    # @return [Integer] price of the things
+    def config_price(start_index, end_index)
+      price = 0
+      @config[start_index..end_index].each_with_index do |presence, index|
+        price += presence * @instance.things[index].price
+      end
+      price
+    end
+
+    # Gets sum of prices of things for which their presence in the knapsack
+    # was not decided yet.
+    #
+    # @param from_index [Integer] index of the first undecided thing
+    # @return [Integer] price of the remaining things
+    def get_price_of_remaining_things(from_index)
+      price = 0
+      to_index = @instance.things.size - 1
+      @instance.things[from_index..to_index].each { |t| price += t.price }
+      price
+    end
+  end
+end
diff --git a/lib/knapsack_solver/solving_methods/dynamic_programming.rb b/lib/knapsack_solver/solving_methods/dynamic_programming.rb
new file mode 100644
index 0000000..756a9a6
--- /dev/null
+++ b/lib/knapsack_solver/solving_methods/dynamic_programming.rb
@@ -0,0 +1,116 @@
+module KnapsackSolver
+  # This class implements methods for solving 0/1 knapsack problem using
+  # dynamic programming with decomposition by price.
+  class DynamicProgramming
+    # Initializes instance of 0/1 knapsack problem solver based on dynamic
+    # programming with decomposition by price.
+    #
+    # @param instance [Instance] 0/1 knapsack problem instance
+    def initialize(instance)
+      @instance = instance
+      @config = Array.new(instance.things.size)
+    end
+
+    # 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)
+    def run
+      solve
+      { price: @best_price, config: @best_config }
+    end
+
+    protected
+
+    # Solve the instance of 0/1 knapsack problem using dynamic programming.
+    def solve
+      # Dynamic programming table
+      c = all_things_price + 1 # height of array from 0 to max. price
+      n = @instance.things.size + 1 # width of array, from 0th thing to Nth
+      # Value used as infinity in the dynamic programming table
+      @infinity = (all_things_weight + 1).freeze
+      @weight_array = Array.new(n) { Array.new(c, @infinity) }
+      @weight_array[0][0] = 0
+      fill_table
+      find_best_price
+      configuration_vector
+    end
+
+    # Fill the dynamic programming table.
+    def fill_table
+      (1..@instance.things.size).each do |ni|
+        (0..all_things_price).each do |ci|
+          @weight_array[ni][ci] = minimum_weight(ni, ci)
+        end
+      end
+    end
+
+    # Find the value of cell in dynamic programming table.
+    #
+    # @param ni [Integer] X axis coordinate
+    # @param ci [Integer] Y axis coordinate
+    # @return [Integer]
+    def minimum_weight(ni, ci)
+      b = weight_of(ni - 1, ci - @instance.things[ni - 1].price)
+      b += @instance.things[ni - 1].weight
+      [weight_of(ni - 1, ci), b].min
+    end
+
+    # Find the best price from the filled dynamic programming table.
+    def find_best_price
+      @best_price = @weight_array.last[0]
+      (1..all_things_price).each do |i|
+        @best_price = i if @weight_array.last[i] <= @instance.weight_capacity
+      end
+    end
+
+    # Reconstructs configuration vector from dynamic programming table.
+    def configuration_vector
+      @best_config = []
+      ci = @best_price
+      @instance.things.size.downto(1) do |i|
+        ci = determine_config_variable(i, ci)
+      end
+    end
+
+    # Determine value of one scalar for the configuration vector.
+    #
+    # return [Integer] next Y index to the dynamic programming table
+    def determine_config_variable(i, ci)
+      if @weight_array[i][ci] == @weight_array[i - 1][ci]
+        @best_config[i - 1] = 0
+      else
+        @best_config[i - 1] = 1
+        ci -= @instance.things[i - 1].price
+      end
+      ci
+    end
+
+    # Gets weight from dynamic programming table.
+    #
+    # @param i [Integer] Y index of dynamic programming table
+    # @param c [Integer] X index of dynamic programming table
+    # @return [Integer] the value from the array
+    def weight_of(i, c)
+      return @infinity if (i < 0) || (c < 0)
+      @weight_array[i][c]
+    end
+
+    # Computes total price of all things of the instance.
+    #
+    # @return [Integer] total price
+    def all_things_price
+      price = 0
+      @instance.things.each { |t| price += t.price }
+      price
+    end
+
+    # Computes total weight of all things of the instance.
+    #
+    # @return [Integer] total weight
+    def all_things_weight
+      weight = 0
+      @instance.things.each { |t| weight += t.weight }
+      weight
+    end
+  end
+end
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
diff --git a/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb b/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb
new file mode 100644
index 0000000..8f694fc
--- /dev/null
+++ b/lib/knapsack_solver/solving_methods/heuristic_price_weight.rb
@@ -0,0 +1,56 @@
+module KnapsackSolver
+  # 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.
+  class HeuristicPriceToWeight
+    # Initializes instance of 0/1 knapsack problem solver using simple
+    # heuristic by price to weight ratio.
+    #
+    # @param instance [Instance] 0/1 knapsack problem instance
+    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
+
+    # 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)
+    def run
+      solve
+      { price: @best_price, config: @best_config }
+    end
+
+    protected
+
+    # Solve the instance of 0/1 knapsack problem.
+    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
+
+    # Gets total weight of things present in the knapsack.
+    #
+    # @return [Integer] total weight
+    def config_weight
+      @config.each_with_index.reduce(0) do |weight, (presence, index)|
+        weight + presence * @instance.things[index].weight
+      end
+    end
+
+    # Gets total price of things present in the knapsack.
+    #
+    # @return [Integer] total price
+    def config_price
+      @config.each_with_index.reduce(0) do |price, (presence, index)|
+        price + presence * @instance.things[index].price
+      end
+    end
+  end
+end