@AlistairIsraelが言ったように、これは解決するのが完全に簡単ではないビンパッキングの問題です。
ただし、以下はこの問題に対する 1 つの解決策です。
アイテムをパッケージ化する方法のすべての組み合わせを検討し、最小限のコストを見つけようとすれば、解決策があります. このソリューションはブルート フォース ソリューションであるため、アイテムの数が増えるとすぐに遅くなることに注意してください。
貨物を異なる箱に分割する方法をすべて見つける。そのために、この回答のアルゴリズムを使用できます。
Python から Ruby へのセットのすべてのパーティションを見つけるための関数の翻訳
次に、すべての異なる組み合わせをループして、最小コストを検索します。ソリューションは次のように機能します。
> optimize_shipping([0.01, 0.01, 0.01, 0.01, 0.12])
Shipping type: courier
Total price : $10
Packaging : [[0.12], [0.01, 0.01, 0.01, 0.01]]
> optimize_shipping([0.01, 0.01, 0.12, 0.15, 0.12])
Shipping type: courier
Total price : $15
Packaging : [[0.01, 0.12], [0.15], [0.01, 0.12]]
> optimize_shipping([0.09, 0.09, 0.01, 0.12, 0.15, 0.12])
Shipping type: courier
Total price : $25
Packaging : [[0.12], [0.15], [0.12], [0.09, 0.01], [0.09]]
> optimize_shipping([0.01, 0.01, 0.01, 0.30])
Shipping type: freight
コード：
COURIER_LIMIT = 0.15
COURIER_PRICE = 5
class Array
def sum
inject(:+)
end
def partitions
yield [] if self.empty?
(0 ... 2 ** self.size / 2).each do |i|
parts = [[], []]
self.each do |item|
parts[i & 1] << item
i >>= 1
end
parts[1].partitions do |b|
result = [parts[0]] + b
result = result.reject do |e|
e.empty?
end
yield result
end
end
end
end
def optimize_shipping(boxes)
if boxes.any? { |b| b > COURIER_LIMIT }
puts "Shipping type: freight"
return
end
# Try and find the cheapest most optimal combination of packaging
smallest_box = 9999
cheapest_price = 9999
cheapest_combination = []
# Go through all paritions and find the optimal distribution
boxes.partitions { |partition|
# Add up sizes per box
sizes = partition.map(&:sum)
# Check if any box got too big for courier, and skip if so
next if sizes.any? { |s| s > COURIER_LIMIT }
# Calculate total price for this combination
total_price = partition.length * COURIER_PRICE
if total_price <= cheapest_price
# Naive algo to try and find best average distriution of items
next if total_price == cheapest_price && sizes.min < smallest_box
# Save this new optimized shipment
smallest_box = sizes.min
cheapest_price = total_price
cheapest_combination = partition
end
}
puts "Shipping type: courier"
puts "Total price : $#{cheapest_price}"
puts "Packaging : #{cheapest_combination.inspect}"
end