44 lines
1.6 KiB
Ruby
44 lines
1.6 KiB
Ruby
KnapsackItem = Struct.new(:name, :weight, :value)
|
|
potential_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],
|
|
]
|
|
knapsack_capacity = 400
|
|
|
|
class Array
|
|
# do something for each element of the array's power set
|
|
def power_set
|
|
yield [] if block_given?
|
|
self.inject([[]]) do |ps, elem|
|
|
ps.each_with_object([]) do |i,r|
|
|
r << i
|
|
new_subset = i + [elem]
|
|
yield new_subset if block_given?
|
|
r << new_subset
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
maxval, solutions = potential_items.power_set.group_by {|subset|
|
|
weight = subset.inject(0) {|w, elem| w + elem.weight}
|
|
weight>knapsack_capacity ? 0 : subset.inject(0){|v, elem| v + elem.value}
|
|
}.max
|
|
|
|
puts "value: #{maxval}"
|
|
solutions.each do |set|
|
|
wt, items = 0, []
|
|
set.each {|elem| wt += elem.weight; items << elem.name}
|
|
puts "weight: #{wt}"
|
|
puts "items: #{items.join(',')}"
|
|
end
|