class KnapsackSolver::DynamicProgramming

This class implements methods for solving 0/1 knapsack problem using dynamic programming with decomposition by price.

Public Class Methods

new(instance) click to toggle source

Initializes instance of 0/1 knapsack problem solver based on dynamic programming with decomposition by price.

@param instance [Instance] 0/1 knapsack problem instance

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 9
def initialize(instance)
  @instance = instance
  @config = Array.new(instance.things.size)
end

Public Instance Methods

run() click to toggle source

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)

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 17
def run
  solve
  { price: @best_price, config: @best_config }
end

Protected Instance Methods

all_things_price() click to toggle source

Computes total price of all things of the instance.

@return [Integer] total price

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 101
def all_things_price
  price = 0
  @instance.things.each { |t| price += t.price }
  price
end
all_things_weight() click to toggle source

Computes total weight of all things of the instance.

@return [Integer] total weight

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 110
def all_things_weight
  weight = 0
  @instance.things.each { |t| weight += t.weight }
  weight
end
configuration_vector() click to toggle source

Reconstructs configuration vector from dynamic programming table.

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 67
def configuration_vector
  @best_config = []
  ci = @best_price
  @instance.things.size.downto(1) do |i|
    ci = determine_config_variable(i, ci)
  end
end
determine_config_variable(i, ci) click to toggle source

Determine value of one scalar for the configuration vector.

return [Integer] next Y index to the dynamic programming table

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 78
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
fill_table() click to toggle source

Fill the dynamic programming table.

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 39
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_best_price() click to toggle source

Find the best price from the filled dynamic programming table.

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 59
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
minimum_weight(ni, ci) click to toggle source

Find the value of cell in dynamic programming table.

@param ni [Integer] X axis coordinate @param ci [Integer] Y axis coordinate @return [Integer]

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 52
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
solve() click to toggle source

Solve the instance of 0/1 knapsack problem using dynamic programming.

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 25
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
weight_of(i, c) click to toggle source

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

# File lib/knapsack_solver/solving_methods/dynamic_programming.rb, line 93
def weight_of(i, c)
  return @infinity if (i < 0) || (c < 0)
  @weight_array[i][c]
end