Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # A greedy algorithm for bin packing
- class Array
- def rest
- self[1..-1]
- end
- end
- def optimize_pack inventory, order
- loop do
- r = pack(inventory, order)
- return r if r
- order += 1
- end
- end
- def pack inventory, order
- case
- when inventory.empty?
- nil
- when order < inventory[0]
- pack(inventory.rest, order)
- when order == inventory.first
- [inventory.first]
- else
- x = pack(inventory.rest, order)
- y = pack(inventory.rest, order - inventory.first)
- choices = []
- choices << x if x
- choices << [inventory.first] + y if y
- choices.min_by { |a| a.length }
- end
- end
- puts nil == pack([], 10)
- puts [10] == pack([10, 5], 10)
- puts [10, 1] == pack([10, 1], 11)
- puts [10, 5] == pack([10, 5, 1], 15)
- puts pack([10, 5, 1], 14)
- puts [10, 5] == optimize_pack([10, 5, 1], 14)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement