diff options
Diffstat (limited to 'lib/knapsack_solver/solving_methods')
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 |