algorithm - 此打包/匹配变体的现有算法？

Question

我有 2 个数组，一个代表元素，另一个代表可以放置元素的箱子:
例如:

ArrayItemSizes = [ 1 2 3 4 ];
ArrayBinSizes = [ 3 3 4 ];

一些规则:

1. 保证 ArrayBinSizes 和 ArrayItemSizes 的总和为相同的数字。(在此示例中，它们的总和为 10)
2. 如果需要，每个项目都可以分解成更小的部分
3. 每件元素仅限于放入箱子中的一件元素(因此元素 1 的一半可以放入箱子，元素 1 的一半可以放入不同的箱子，但元素 1 仅此而已)
4. 每件元素都必须完全放入垃圾箱。

棘手的部分是我希望它具有最少数量的唯一项 - bin 配对。
因此，如果 ArrayItemSizes( 1 ) 被分成 3 个不同的容器，那将导致 3 个项目 -> 容器配对:

1. 项目 1 - bin 1
2. 项目 1 - bin 2
3. 项目 1 - bin 3

这比将项目 1 放入 1 个箱子更不理想，后者只会创建 1 个项目 - 箱子对。

一个好的解决方案应该是这样的:

ArrayItemSizes( 1 ) in ArrayBinSizes ( 1 )  
ArrayItemSizes( 2 ) in ArrayBinSizes ( 1 )  
ArrayItemSizes( 3 ) in ArrayBinSizes ( 2 )  
ArrayItemSizes( 4 ) in ArrayBinSizes ( 3 ) 

它具有最少数量的可能项目 - bin 配对(4 对)，并使用所有项目。

一个不受欢迎的解决方案是这样的:

A fraction of ArrayItemSizes( 1 ) in ArrayBinSizes ( 1 )  
A fraction of ArrayItemSizes( 1 ) in ArrayBinSizes ( 2 )  
A fraction of ArrayItemSizes( 1 ) in ArrayBinSizes ( 3 )  
A fraction of ArrayItemSizes( 2 ) in ArrayBinSizes ( 1 )  
A fraction of ArrayItemSizes( 2 ) in ArrayBinSizes ( 2 )  
A fraction of ArrayItemSizes( 2 ) in ArrayBinSizes ( 3 )  

等等……

这会创建比必要更多的项目 - bin 配对并且是不可取的(6 只用于前 2 个项目)。将元素分成不同的箱子通常是不可取的，因为这会增加对数，尽管通常有必要打包所有东西。

我无法弄清楚如何表示这个问题。我研究了图形对匹配问题和背包/包装问题，但没有一个完全匹配。

解决这个问题的好方法是什么？我应该研究优化问题求解器、动态规划、图形算法还是其他东西？

Answer 1

您可以尝试用于机器托管的共享感知算法:http://research.google.com/pubs/pub37147.html .