如何找到满足要求的项目组合?

问题描述 投票:1回答:1

我在编程上相当新,所以我希望有人能指出我正确的方向。

我有一个约2400人的名单,每个人至少有23个条件中的一个(如果他们有条件,每个人的条件是1或如果他们没有条件,则为0)。

例如。如果Jon有条件1,5和6,Jon的输出将是{1,0,0,0,1,1,0,0 ...}。

然后,我将获得一份列表,列出每种病情的人数。因此,如果条件1的期望数量是10个人且条件2的期望数量是5个人,我希望10个条件1和5个人具有条件2(一个人可以计入条件1并且条件2如果他们两个都有) 。

此外,我必须选择正好30个人并尽可能接近所需数量的条件,严格限制一个条件必须至少有三个人,不超过10个人。

有没有办法可以做到这一点,如果是这样,我将如何去做呢?我试图强制执行此操作,但是大量的组合使我无法获得解决方案。

编辑:这是一个小例子,包含5个人和4个条件的列表:

Person 1: {1,0,0,1} Person 2: {0,1,1,1} Person 3: {0,0,0,1} Person 4: {1,0,0,0} Person 5: {1,0,0,1}

期望的条件数{2,1,1,2}。我的想法是,我需要选择3个人,并尽可能接近所需数量的条件。在该示例中,将选择人1,2和4。我必须将这个想法扩展到包含23个条件并选择30个人的2400人的列表(尽管它应该能够扩展到任何列表大小和任意数量的条件)并且不知道是否有30个成员的组合这将导致完全匹配。

这有助于澄清事情吗?

python-3.x satisfiability constraint-satisfaction
1个回答
0
投票

约束编程可以很容易地解决这个问题。由于您使用的是Python,因此可以使用Google's CP solver。在2400人的情况下,您将拥有30个决策变量,每个变量具有2400个值的域。您的目标是最小化您的解决方案与理论最优解决方案之间的差异(得分为0意味着完全满足所有23个条件)。通过使用约束编程,可以通过几十行代码实现。求解器将处理搜索策略和其他细节。

© www.soinside.com 2019 - 2024. All rights reserved.