时间戳

首页 > 解决方案 > 利润取决于分配的多对一分配问题

algorithm - 利润取决于分配的多对一分配问题

问题描述

很抱歉在短时间内提出类似的问题。这个问题与我之前的帖子类似，但略有不同。

它仍然是M任务和N人的多对一匹配问题。每个任务只能分配给一个人，一个人可以获得多个任务。但是，在分配任务时有三种不同的利润，一种为任务本身，一种为获得任务的人，一种为整体收益。这三个利润可以是正的也可以是负的。只有当任务和人的利润总和为正时，才能将任务分配给一个人。此外，任务和人的利润取决于分配给一个人的任务的组合。目标是最大化总利润的总和。

例如，如果任务i分配给人员j，我们表示G ={ i , j }。然后，任务得到 P G->i，人得到 P G->j，整体收益是 P G =P G->j +P G->i。如果是这种情况，P G->j、 P G->i和 P G必须是正数。否则，分配应该失败。

另一个例子：如果我们有两个任务i，i+1和一个人j，我们可以有可能的分配：G 1 ={ i , j }, G 2 ={ i+1 , j } 和G 3 ={我,我+1 , j }。假设 P G 1 ->j , P G 1 ->i , P G 1 , P G 2 ->i+1 , P G 2是正数，而 P G2 ->j为负数，则可以使用以下赋值：

  1. 仅将任务i分配给人员j。
  2. 如果 P G 3 ->j > 0 且 P G 3 > P G 1则将任务i和i+1分配给人员j。注意 P G 3 ->j不等于 P G 2 ->j +P G 1 ->j并且 P G 3不等于 P G 1 + P G 2。

注意：将任务i+1分配给人员j是不可能的，因为 P G 2 ->j < 0。

“P G 3不等于 P G 1 + P G 2 ”表示每次尝试分配一个加法任务给一个人时，我们都需要重新计算利润（与我上一篇文章中的问题不同）。我们仍然可以通过贪心算法获得次优解。但是，我想知道这是否是一个 NP 难题，因为似乎获得最佳解决方案的唯一方法是对所有组合进行全面搜索，这表明计算开销非常高。

除了对所有组合的完全搜索之外，是否有任何多项式时间算法可以解决这个问题？

标签： algorithmmany-to-one

解决方案

推荐阅读