knapsack_solver.rb

# Based on http://rosettacode.org/wiki/Knapsack_problem/Bounded#Dynamic_programming_solution
# https://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_knapsack_problem
class KnapsackSolver
  attr_reader :table, :items, :limit
  # items: [{weight: <whole integer weight>, value: <any numeric value to maximize>}]
  # limit: <whole integer weight limit>
  #
  # For money, you can * 100 to optimize to the cent
  # but then the runtime increases by x100
  # You can also re-normalize based on the bounds/resolution,
  # but it's easier to work in whole dollars here
  # (and the difference is not severe)
  def initialize(items, limit)
    @items = items
    @limit = limit
  end

  def solve_linear
    return items if limit.respond_to?(:infinite?) && limit.infinite?
    @table = Array.new(items.count + 1) { Array.new(limit + 1) { 0 } }

    1.upto(items.count) do |j|
      item = items[j - 1]
      weight, value = item.values_at(:weight, :value)
      1.upto(limit) do |w|
        if weight > w
          table[j][w] = table[j - 1][w]
        else
          table[j][w] = [table[j - 1][w], table[j - 1][w - weight] + value].max
        end
      end
    end

    result = []
    w = limit

    items.count.downto(0) do |j|
      was_added = table[j][w] != table[j - 1][w]

      if was_added
        item = items[j - 1]
        result << item
        w -= item[:weight]
      end
    end

    result
  end

  def solve_recursive
    @table = [].tap { |m| (items.count+1).times { m << {} } }

    def recursive_inner(index, inner_limit, selected = [])
      return 0 if index == 0
      return 0 if inner_limit == 0

      item = items[index]
      weight, value = item.values_at(:weight, :value)

      stored_value = @table[index - 1][inner_limit]
      return stored_value unless stored_value.nil?

      # This item doesn't fit at current limit
      if weight > inner_limit
        return @table[index - 1][inner_limit] = recursive_inner(index - 1, inner_limit, selected)
      # This item does
      else
        # Choose a higher value item later?
        option_1  = recursive_inner(index - 1, inner_limit, selected)
        # Choose this item?
        option_2  = value + recursive_inner(index - 1, inner_limit - weight, selected)

        if option_1 > option_2
          @table[index - 1][inner_limit] = option_1
          return option_1
        else
          selected << item
          @table[index - 1][inner_limit] = option_2
          return option_2
        end
      end
    end

    binding.pry

    result = []
    w = limit

    items.count.downto(0) do |j|
      was_added = table[j - 1][w] != table[j - 2][w]

      if was_added
        item = items[j - 2]
        result << item
        w -= item[:weight]
      end
    end

    selected = []
    recursive_inner(items.count - 1, limit, selected)
    selected
  end

#   def knapsack_cached(rows, knapsack_size, index)
#   return 0 if knapsack_size == 0 || index == 0
#   value, weight = rows[index]
#   if weight > knapsack_size
#     stored_value = @new_cache[index-1][knapsack_size]

#     return stored_value unless stored_value.nil?
#     return @new_cache[index-1][knapsack_size] = knapsack_cached(rows, knapsack_size, index-1)
#   else
#     stored_value = @new_cache[index-1][knapsack_size]
#     return stored_value unless stored_value.nil?

#     option_1  = knapsack_cached(rows, knapsack_size, index-1)
#     option_2  = value + knapsack_cached(rows, knapsack_size - weight, index-1)
#     return @new_cache[index-1][knapsack_size] = [option_1, option_2].max
#   end
# end
end


# load "lib/knapsack_solver.rb"
items = 100.times.map{|i| {weight: rand(100), value: rand(100)}};
limit = 1000

KnapsackSolver.new(items, limit).solve_linear
KnapsackSolver.new(items, limit).solve_recursive