灌装桶与同等尺寸 [英] Filling bins with an equal size
问题描述
我有100组,每组有里面的一些元素。对于交叉验证,我想提出五个组,他们的尺寸尽可能相等。
I have 100 groups and each group has some elements inside. For the cross validation, I want to make five bins which their size is as equal as possible.
有什么算法用于此目的。
Is there any algorithm for this purpose.
5组和2箱一个例子:
An example for 5 groups and 2 bins:
Group_1: 5
Group_2: 6
Group_3: 2
Group_4: 7
Group_5: 1
这两个桶将是:
The two bins will be:
G1和G2 - >他们的总和等于11
G1 and G2 -> their sum is equal to 11.
G3,G4和G5。 - >他们的总和等于10
G3, G4 and G5 -> their sum is equal to 10.
推荐答案
这似乎涉及到设置划分问题,这是 NP -hard幸好承认很多很好的近似算法和伪多项式时间动态规划算法。你可能想看看那些为出发点,因为有已经相当大量的工作是在这方面开展的工作。
This seems related to the set partitioning problem, which is NP-hard but fortunately admits lots of good approximation algorithms and pseudopolynomial-time dynamic programming algorithms. You may want to look into those as a starting point, since there's already quite a lot of work that's been done in this area.
希望这有助于!
这篇关于灌装桶与同等尺寸的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!