运输尺寸组合

Question

我有一堆尺寸可以发货的产品,我需要找出最便宜的价格.

鉴于货物是用大小装运的,比如[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

我想你想生成一组的分区.

这是非常好的解释和工作代码.

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

有 这样的事情n.

我认为你有一个背包问题,动态编程是解决问题的正确方法.