哪种软件算法将从一个大集合中选择一个不同的项目子集

Question

设置

假设我有很多物品。每件物品都有形状、大小和颜色。他们可能是

• 三角形、圆或正方形
• 红、绿或蓝
• 小还是大

对于这些属性在项目中的分布，我不能做任何假设。我相当肯定，它不是一百万个大的，红色的三角形，但这是一种可能性。

问题

我想在所有属性类中选择36个尽可能具有“多样性”表示的形状。为了澄清，36个项目从非常大的集合我想要12个红色，12个绿色，12个蓝色，12个三角形，18个小等等。

现在有18种可能不同的项目类型(3种颜色*3种形状*2种大小)，所以一种方法是包括两种不同的类型(假设我有它们)。

如果我没有足够的每一种不同的类型，另一种(不切实际的，蛮力)方法，将迭代每一个可能的子集36项，并保持最佳子集。

我确信，这是一个具体的例子，一个更广泛的问题类别，可以由一个众所周知的算法解决，但我不能确定谷歌的神奇词汇。我将其标记为knapsack-problem，因为感觉上可能是这样，但我不知道是否有更好的方法来解决这个问题？

您能帮助解决方案或至少适当的搜索术语吗？

Answer 1

看看储层取样。为每个形状/颜色/大小组合(所以36个储油层)制造一个储油层，每个储油层具有36个容量。对所有元素进行一次检查，并为每个元素选择合适的存储库并执行储油层取样步骤。

这将您的问题减少到最多36*36 = 1296元素，从所有元素中公平抽样，甚至涵盖了最坏的情况，其中只有一个组合。

然后，您可以简单地洗牌，从每个库中选择一个随机元素(跳过空库)，将它们从库中移除。如果您有每种形状/颜色/大小之一，则立即完成。如果没有，您将再次洗牌并执行另一次传递，并一直这样做，直到您选择了36个元素。这为您提供了数据集上的统一样本，该样本由形状/颜色/大小偏差进行规范化。