ruby - 运输尺寸组合

Question

我有一堆需要发货的产品，我需要找出最便宜的价格。

给定一批由尺寸组成的 cargo ，比如说 [1,3,3,5] 我需要决定如何运送 - 一起运送还是分开运送。然而，它不像 [1,3,3,5] 或 1 & 3 & 3 & 5 那样简单，我需要所有可能的组合，例如:

[
[[1,3,3,5]],           ( 1 shipment )
[[1],[3,3,5]],         ( 2 shipments )
[[1,3],[3,5]],         ( 2 shipments )
[[1,3,3],[5]],         ( 2 shipments )
[[1,5],[3,3]],         ( 2 shipments ) 
[[1,3],[3],[5]],       ( 3 shipments )
[[1],[3],[3],[5]]      ( 4 shipments )
]

(等 - 我想还有更多)我已经尝试了 facets gem 的组合，但这并不是我想要的，而且我不确定如何解决这个问题。我知道它可能有一个名字和一个解决方案，如果我知道这个名字的话:)

我知道可能有很多组合，但初始大小数组不会大于 7 个左右。

提前致谢!

Answer 1

我猜你想生成 the partitions of a set .

Here is very good explanation and working code to do it.

但这样做并不是一个好主意，因为它会导致 Combinatorial Explotion .

有 n 这样的东西。

我想你有一个 knapsack problem 和 dynamic programming是解决问题的正确方法。