将 m 个学生影响到 n 个组，但有限制？
Affect m students to n groups, but with constraints?
我询问了最低成本最大流量 . Kraskevich's answer was brilliant and solved my problem. I've implemented it，它工作正常（仅提供法语版本，抱歉）。此外，该算法可以处理 i（i > 1）项目分配给每个学生。
现在我正在尝试更困难的事情。我想添加对选择的限制。如果有人想影响每个学生的 i (i > 1) 个项目，我希望能够指定哪些项目是兼容（彼此）。
在某些项目不兼容的情况下，我希望算法 return 全局最优，即影响每个学生的 i 个项目，使全局幸福最大化和 尊重兼容性限制。
将原始方法链接 i 次（并在每一步检查约束条件）无济于事，因为它只会 return 局部最优。
知道要使用的正确图形吗？
不幸的是，它在多项式时间内不可解（除非P = NP或有额外的约束）。
这是从最大独立集问题（已知是 NP 完全问题）到这个问题的多项式时间缩减：
给定一个图表 G 和一个数字 k，执行以下操作：
为图中的每个顶点创建一个项目 G 并说两个项目不兼容，前提是 G 中对应的顶点之间存在一条边。
创造一个对每个项目都同样喜欢的学生（我们可以假设每个项目给他的快乐等于1）。
使用解决问题中所述问题的算法找到最大的幸福感。我们称它为 h.
可以选择一组项目，前提是它们都兼容，这意味着 G 的选择顶点形成一个独立的集合（由于我们构建图形的方式）。
因此，h等于最大独立集的大小
Returnh >= k。
这在实践中意味着什么？这意味着寻找这个问题的多项式时间解是不合理的。可以做几件事：
如果输入较小，可以使用穷举搜索
如果不是，您可以使用启发式 and/or 近似来找到相对较好的解决方案（但不一定是最佳解决方案）。
如果您能忍受库依赖性，整数编程将比您自己实现的任何东西都更快、更容易。您所要做的就是将原始问题表述为整数规划，然后在最后添加您的临时约束。
我询问了最低成本最大流量
现在我正在尝试更困难的事情。我想添加对选择的限制。如果有人想影响每个学生的 i (i > 1) 个项目，我希望能够指定哪些项目是兼容（彼此）。
在某些项目不兼容的情况下，我希望算法 return 全局最优，即影响每个学生的 i 个项目，使全局幸福最大化和 尊重兼容性限制。
将原始方法链接 i 次（并在每一步检查约束条件）无济于事，因为它只会 return 局部最优。
知道要使用的正确图形吗？
不幸的是，它在多项式时间内不可解（除非P = NP或有额外的约束）。
这是从最大独立集问题（已知是 NP 完全问题）到这个问题的多项式时间缩减：
给定一个图表 G 和一个数字 k，执行以下操作：
为图中的每个顶点创建一个项目
G并说两个项目不兼容，前提是G中对应的顶点之间存在一条边。创造一个对每个项目都同样喜欢的学生（我们可以假设每个项目给他的快乐等于
1）。使用解决问题中所述问题的算法找到最大的幸福感。我们称它为
h.可以选择一组项目，前提是它们都兼容，这意味着
G的选择顶点形成一个独立的集合（由于我们构建图形的方式）。因此，
h等于最大独立集的大小Return
h >= k。
这在实践中意味着什么？这意味着寻找这个问题的多项式时间解是不合理的。可以做几件事：
如果输入较小，可以使用穷举搜索
如果不是，您可以使用启发式 and/or 近似来找到相对较好的解决方案（但不一定是最佳解决方案）。
如果您能忍受库依赖性，整数编程将比您自己实现的任何东西都更快、更容易。您所要做的就是将原始问题表述为整数规划，然后在最后添加您的临时约束。