多对一分配问题是 NP 难的吗？
Is a many to one assignment problem NP-hard?
如果有人问过类似的问题，我深表歉意。我正在解决 N 任务和 M 人的多对一分配问题。每个人可以得到多个任务，而每个任务只能分配给一个人。如果任务i分配给人j.[=10，我们可以赚取利润Pij =]
我知道一对一的分配可以在多项式时间内通过匈牙利算法得到最优解。我认为这个问题比一对一分配问题更难，也是广义分配问题（GAP）的一个特例，我们对一个人可以分配的任务数量没有限制。 （当然，我们可以限制一个人的任务数量，但这种情况下每个任务的权重是相同的，所以仍然是GAP的特例。）
我相信我们可以通过应用启发式方法来获得次优解决方案，无论是否限制分配给一个人的任务数量，但是是否有任何算法可以在多项式时间内解决这个问题？这个问题是 NP-hard 问题吗？
广义分配问题很难，因为任务大小不同。自然线性规划存在完整性差距
这个问题没有这样的差距，实际上可以表述为最小成本循环问题的一个实例，可在强多项式时间内求解。假设任务利润是正的（不失一般性，通过给一个任务的所有潜在利润加上一个常量），建立一个网络，每个任务一个节点，每个人一个节点，source/sink.从 source/sink 到每个任务有一个容量弧 1，成本为 0。从每个任务 i 到每个人 j 有一个无界容量弧，成本为 −Pij。从每个人到 source/sink 有一条弧线，其容量等于该人可以完成的任务数，成本为 0.
要获得解决方案，请顺畅地阅读任务。
如果有人问过类似的问题，我深表歉意。我正在解决 N 任务和 M 人的多对一分配问题。每个人可以得到多个任务，而每个任务只能分配给一个人。如果任务i分配给人j.[=10，我们可以赚取利润Pij =]
我知道一对一的分配可以在多项式时间内通过匈牙利算法得到最优解。我认为这个问题比一对一分配问题更难，也是广义分配问题（GAP）的一个特例，我们对一个人可以分配的任务数量没有限制。 （当然，我们可以限制一个人的任务数量，但这种情况下每个任务的权重是相同的，所以仍然是GAP的特例。）
我相信我们可以通过应用启发式方法来获得次优解决方案，无论是否限制分配给一个人的任务数量，但是是否有任何算法可以在多项式时间内解决这个问题？这个问题是 NP-hard 问题吗？
广义分配问题很难，因为任务大小不同。自然线性规划存在完整性差距
这个问题没有这样的差距，实际上可以表述为最小成本循环问题的一个实例，可在强多项式时间内求解。假设任务利润是正的（不失一般性，通过给一个任务的所有潜在利润加上一个常量），建立一个网络，每个任务一个节点，每个人一个节点，source/sink.从 source/sink 到每个任务有一个容量弧 1，成本为 0。从每个任务 i 到每个人 j 有一个无界容量弧，成本为 −Pij。从每个人到 source/sink 有一条弧线，其容量等于该人可以完成的任务数，成本为 0.
要获得解决方案，请顺畅地阅读任务。