64 lines
2.6 KiB
Ruby
64 lines
2.6 KiB
Ruby
KnapsackItem = Struct.new(:name, :weight, :value)
|
|
|
|
def dynamic_programming_knapsack(items, max_weight)
|
|
num_items = items.size
|
|
cost_matrix = Array.new(num_items){Array.new(max_weight+1, 0)}
|
|
|
|
num_items.times do |i|
|
|
(max_weight + 1).times do |j|
|
|
if(items[i].weight > j)
|
|
cost_matrix[i][j] = cost_matrix[i-1][j]
|
|
else
|
|
cost_matrix[i][j] = [cost_matrix[i-1][j], items[i].value + cost_matrix[i-1][j-items[i].weight]].max
|
|
end
|
|
end
|
|
end
|
|
used_items = get_used_items(items, cost_matrix)
|
|
[get_list_of_used_items_names(items, used_items), # used items names
|
|
items.zip(used_items).map{|item,used| item.weight*used}.inject(:+), # total weight
|
|
cost_matrix.last.last] # total value
|
|
end
|
|
|
|
def get_used_items(items, cost_matrix)
|
|
i = cost_matrix.size - 1
|
|
currentCost = cost_matrix[0].size - 1
|
|
marked = cost_matrix.map{0}
|
|
|
|
while(i >= 0 && currentCost >= 0)
|
|
if(i == 0 && cost_matrix[i][currentCost] > 0 ) || (cost_matrix[i][currentCost] != cost_matrix[i-1][currentCost])
|
|
marked[i] = 1
|
|
currentCost -= items[i].weight
|
|
end
|
|
i -= 1
|
|
end
|
|
marked
|
|
end
|
|
|
|
def get_list_of_used_items_names(items, used_items)
|
|
items.zip(used_items).map{|item,used| item.name if used>0}.compact.join(', ')
|
|
end
|
|
|
|
if $0 == __FILE__
|
|
items = [
|
|
KnapsackItem['map' , 9, 150], KnapsackItem['compass' , 13, 35],
|
|
KnapsackItem['water' , 153, 200], KnapsackItem['sandwich' , 50, 160],
|
|
KnapsackItem['glucose' , 15, 60], KnapsackItem['tin' , 68, 45],
|
|
KnapsackItem['banana' , 27, 60], KnapsackItem['apple' , 39, 40],
|
|
KnapsackItem['cheese' , 23, 30], KnapsackItem['beer' , 52, 10],
|
|
KnapsackItem['suntan cream' , 11, 70], KnapsackItem['camera' , 32, 30],
|
|
KnapsackItem['t-shirt' , 24, 15], KnapsackItem['trousers' , 48, 10],
|
|
KnapsackItem['umbrella' , 73, 40], KnapsackItem['waterproof trousers', 42, 70],
|
|
KnapsackItem['waterproof overclothes', 43, 75], KnapsackItem['note-case' , 22, 80],
|
|
KnapsackItem['sunglasses' , 7, 20], KnapsackItem['towel' , 18, 12],
|
|
KnapsackItem['socks' , 4, 50], KnapsackItem['book' , 30, 10]
|
|
]
|
|
|
|
names, weight, value = dynamic_programming_knapsack(items, 400)
|
|
puts
|
|
puts 'Dynamic Programming:'
|
|
puts
|
|
puts "Found solution: #{names}"
|
|
puts "total weight: #{weight}"
|
|
puts "total value: #{value}"
|
|
end
|