60 lines
1.7 KiB
Ruby
60 lines
1.7 KiB
Ruby
# Item struct to represent each item in the problem
|
|
Struct.new('Item', :name, :weight, :value, :count)
|
|
|
|
$items = [
|
|
Struct::Item.new('map', 9, 150, 1),
|
|
Struct::Item.new('compass', 13, 35, 1),
|
|
Struct::Item.new('water', 153, 200, 3),
|
|
Struct::Item.new('sandwich', 50, 60, 2),
|
|
Struct::Item.new('glucose', 15, 60, 2),
|
|
Struct::Item.new('tin', 68, 45, 3),
|
|
Struct::Item.new('banana', 27, 60, 3),
|
|
Struct::Item.new('apple', 39, 40, 3),
|
|
Struct::Item.new('cheese', 23, 30, 1),
|
|
Struct::Item.new('beer', 52, 10, 3),
|
|
Struct::Item.new('suntan cream', 11, 70, 1),
|
|
Struct::Item.new('camera', 32, 30, 1),
|
|
Struct::Item.new('t-shirt', 24, 15, 2),
|
|
Struct::Item.new('trousers', 48, 10, 2),
|
|
Struct::Item.new('umbrella', 73, 40, 1),
|
|
Struct::Item.new('w-trousers', 42, 70, 1),
|
|
Struct::Item.new('w-overcoat', 43, 75, 1),
|
|
Struct::Item.new('note-case', 22, 80, 1),
|
|
Struct::Item.new('sunglasses', 7, 20, 1),
|
|
Struct::Item.new('towel', 18, 12, 2),
|
|
Struct::Item.new('socks', 4, 50, 1),
|
|
Struct::Item.new('book', 30, 10, 2)
|
|
]
|
|
|
|
def choose_item(weight, id, cache)
|
|
return 0, [] if id < 0
|
|
|
|
k = [weight, id]
|
|
return cache[k] unless cache[k].nil?
|
|
value = $items[id].value
|
|
best_v = 0
|
|
best_list = []
|
|
($items[id].count+1).times do |i|
|
|
wlim = weight - i * $items[id].weight
|
|
break if wlim < 0
|
|
val, taken = choose_item(wlim, id - 1, cache)
|
|
if val + i * value > best_v
|
|
best_v = val + i * value
|
|
best_list = taken + [i]
|
|
end
|
|
end
|
|
cache[k] = [best_v, best_list]
|
|
return [best_v, best_list]
|
|
end
|
|
|
|
val, list = choose_item(400, $items.length - 1, {})
|
|
w = 0
|
|
list.each_with_index do |cnt, i|
|
|
if cnt > 0
|
|
print "#{cnt} #{$items[i].name}\n"
|
|
w += $items[i][1] * cnt
|
|
end
|
|
end
|
|
|
|
p "Total weight: #{w}, Value: #{val}"
|