Skip to content

Instantly share code, notes, and snippets.

@xullnn

xullnn/knapsack.rb

Last active Apr 27, 2018
Embed
What would you like to do?
the knapsack problem
class Item
attr_accessor :name, :weight, :price
end
class Knapsack
attr_accessor :items, :capacity, :table
def initialize(capacity)
@items = []
@capacity = capacity
@table = Hash.new([0, [nil]])
end
def fill_items
return "No available items" if items.empty?
items.each_with_index do |item, index|
row = index + 1
(1..capacity).each do |column|
previous_max_value = table[[row-1, column]][0]
previous_max_name = table[[row-1, column]][1]
if column < item.weight
table[[row, column]] = table[[row-1, column]]
elsif column == item.weight
new_value = item.price
new_value >= previous_max_value \
? table[[row, column]] = [new_value, [item.name]] \
: table[[row, column]] = [previous_max_value, previous_max_name]
else
diff_weight = column - item.weight
diff_item_name = table[[row-1, diff_weight]][1]
diff_item_value = table[[row-1, diff_weight]][0]
new_value = item.price + diff_item_value
if diff_item_value == 0
table[[row, column]] = [new_value, [item.name]]
else
table[[row, column]] = [new_value, diff_item_name + [item.name]]
end
end
end
end
end
def find_best_combinations
sorted_table = table.sort_by { |k, v| v[0] } # return an array
max_combination_price = sorted_table[-1][1][0]
p best_combinations = table.select { |k, v| v[0] == max_combination_price }
end
end
guitar = Item.new; guitar.weight = 1; guitar.price = 1500; guitar.name = "guitar"
laptop = Item.new; laptop.weight = 3; laptop.price = 2000; laptop.name = "laptop"
stereo = Item.new; stereo.weight = 4; stereo.price = 3000; stereo.name = "stereo"
headphone = Item.new; headphone.weight = 2; headphone.price = 500; headphone.name = "headphone"
necklace = Item.new; necklace.weight = 1; necklace.price = 2500; necklace.name = "necklace"
knapsack = Knapsack.new(4)
knapsack.items = [stereo,laptop,guitar,headphone,necklace].shuffle
knapsack.fill_items
knapsack.find_best_combinations
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment