Created
November 11, 2015 16:56
-
-
Save perplexes/bbba49e4094ea3d8a13f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment