↖️ Show all posts

# Super Simple Knapsack Ruby

Knapsack? What sack?

Wikipedia says:

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.

main.rb

``````# main.rb

require_relative 'simple_knapsack'

input_data = [
{
l: 12,
v: 4
},
{
l: 2,
v: 2
},
{
l: 1,
v: 2
},
{
l: 1,
v: 1
},
{
l: 4,
v: 10
}
]

limit = 15

ksack = SimpleKnapsack.new(limit, input_data)
result = ksack.calculate
puts result[:result][:score_v] == 15
puts result[:result][:score_l] == 8

input_data = [
{
l: 75,
v: 76
},
{
l: 50,
v: 50
},
{
l: 50,
v: 50
}
]

limit = 100

ksack = SimpleKnapsack.new(limit, input_data, debug: true)
result = ksack.calculate
puts result[:result][:score_v] == 100
puts result[:result][:score_l] == 100
``````

simple_knapsack.rb

``````# simple_knapsack.rb

class SimpleKnapsack
def initialize(limit, data, debug: false)
@limit = limit
@data = data
validate_data_structure! if debug
@data_with_ratios = calc_ratios
@results = []
end

def validate_data_structure!
puts 'Debug mode: ON!, raising error when receiving malformed data!'
Integer(item[:v]) && Integer(item[:l])
end
end

def calculate
return calculate_relative_value if in_sacks_limits?(score_item_key(:l, @data))

best_combination_score = calculate_combinations
@results.max { |r| r[:result][:score_v] }
end

private

def track_result(method_name, result)
@results.push({ method: method_name.to_sym, result: })
result
end

def calculate_combinations
best_results = nil
current_v_score = 0
current_l_score = 0

(1..(@data_with_ratios.count - 1)).each do |i|
@data_with_ratios.combination(i).each do |combination|
v_score = score_item_key(:v, combination)
l_score = score_item_key(:l, combination)

next unless v_score > current_v_score && l_score <= @limit

current_v_score = v_score
current_l_score = l_score
best_results = combination.map(&:dup)
end
end

track_result(:calculate_combinations, build_result_hash(items: best_results))
end

def calculate_relative_value
result = []
rich_data = @data_with_ratios.sort_by { |d| d[:ratio] }.map(&:dup)
result.push(rich_data.pop) while sum_up_while_in_given_limit(result)
result.pop while in_sacks_limits?(score_item_key(:l, result))

track_result(:calculate_relative_value, build_result_hash(items: result))
end

def score_item_key(k, result)
result.sum { |entry| entry[k] }
end

def calc_ratios
@data.map do |d|
ddup = d.dup
ddup[:ratio] = Rational(ddup[:v], ddup[:l])
ddup
end
end

def build_result_hash(items:)
{
items:,
score_v: score_item_key(:v, items),
score_l: score_item_key(:l, items)
}
end

def sum_up_while_in_given_limit(result_data)
return true if result_data.empty? || in_sacks_limits?(score_item_key(:l, result_data))
end

def in_sacks_limits?(val)
val < @limit
end
end
``````