c++ - 拆分一个集合，对于每个子集，尊重其项目属性的概率

Question

对于一个小游戏(我有点被迫使用 C++，所以基于 STL 的解决方案在这里可能很有趣)，我遇到了以下巧妙的问题。我想知道是否有我可以阅读的有关该主题的任何文献或巧妙的实现。

独特项目{E1, E2, E3}的集合S，每个项目E都有一组属性，{P1, P2, P3...}
此集合应分为 S1、S2、S3、S4。它定义了 S1..4 必须有多大。对于剩下的问题，我们可以假设集合可以按这些大小正确拆分。

现在，对于 S1，可以出现许多约束，{C1, C2..}，它们指定例如，具有属性 P1 的项目不得出现在其中。另一个约束可能是它应该有利于具有系数为 0.8 的属性 P2 的项目(我们可以假设这些类型的约束针对每个属性的所有子集进行了归一化)。

“加权”并不难实现。我只是用候选数字填充一些数组，权重较高的那些在这个数组中表示得更多。然后我选择数组的一个随机元素。数组的大小决定了准确性/粒度(在我的例子中，一个小数组就足够了)。

问题是禁止某些项目出现。它很容易导致 S 中的一项需要放在子集 S1、S2、S3 或 S4 之一中的情况，但这种情况不会再发生，因为子集要么全满，要么未满full 有一个特定的约束，即该项目不能出现在集合中。所以你必须回溯放置。经常这样做可能会严重违反加权概率。

这个问题是如何命名的，或者它是否容易映射到另一个(可能是 NP)问题？

编辑:示例:

S = {A、B、C、D、E、F、G、H、I、J、K、L、M}

S1 = [ 0.8 有元音的概率，不能有 I 或 K，SIZE = 6 ]
S2 = [ 0.2 有元音的概率，不能有 M, B, E, SIZE = 7 ]

现在，假设我们通过 FOR(LETTER IN S) 开始填充:

LETTER A，根据属性约束创建一个填充数组(0.8 vs 0.2):
[ 1, 1, 1, 1, 1, 1, 1, 2, 2]。
从该数组中选择一个随机元素: 1.

现在，将 A 放入 S1。

例如，对于字母 I，唯一的候选者是 2，因为 S1 有一个限制，我不能出现在其中。

继续这样做，最终你可能会得到:
C = { M }//再分发一封信

S1 = A、B、D、E、F、G
S2 = C, F, G, I, K, L

现在，把 M 放在哪里？ I tcannot be placed in S1, since the one is full, and it cannot placed in S2 because it has a constraint that M cannot be placed in it.
唯一的方法是回溯一些位置，但那样我们可能会过多地扰乱加权分布(例如，给 S2 一个 S1 的元音，这会翻转自然分布)

请注意，当有更多子集在运行时，这会变得稍微复杂一些(在需要更多回溯的意义上)，而不仅仅是 2 个。

Answer 1

这类似于具有硬约束和软约束的约束满足问题 (CSP)。有几个标准算法，但您必须检查它们是否适用于您的特定问题实例。

检查 wikipedia对于初学者。