找到最大幸福总和的问题 [英] Problem with finding maximal sum of happiness

问题描述

我有一个问题要解决，并没有看到任何最佳解决方案：/问题是：


我有n个工人和k个工作。每项工作都由指定数量的工人完成，每个工人对每项工作都有自己的幸福感。我必须制定工作时间表，以便工人尽可能快乐。

所以，我有一个int [n，k]的数组a1。第i行的第k列包含第i个工作者对第k个工作的偏好（从0到10的数字）。我也有int [k]的数组a2，其中第i个元素包含将要完成这项工作的人数。我必须找到最大可能的幸福总和，知道n> = min（a2）。

我的解决方案是使用递归。为第一个作业组合选择第一个工作人员，向总和添加首选项，检查总和是否高于已找到的最大值，如果是，则转到下一个工作人员。返回时，请检查第一个工作人员的下一个组合等。这适用于少量工作人员，但必须具有高计算复杂度才能解决更大的问题。您有什么想法可以获得更好的解决方案吗？

Hi, I have a problem to solve, and do not see any optimal solution :/ The problem is:

I have n workers and k jobs. Each job is to be done by specified number of workers, and each worker has his level of happines for each job. I have to to make a work schedule so that workers would be as happy as possible.
So, I have array a1 of int[n,k]. k-th column of i-th row contains preference (number from 0 to 10) of i-th worker for k-th job. I also have array a2 of int[k], where i-th element contains number of people who will be doing that job. I have to find maximal possible sum of happines, knowing that n >= min(a2).
My solution is to use recursion. Select first worker for first combination of jobs, add preferences to the sum, check if sum is higher then maximal already found, and if it is, go to the next worker. When back, check the next combination for the first worker etc. This works fine for small amount of workers, but has to high computational complexity to solve bigger problems. Have You got any idea for better solution?

推荐答案

您所拥有的是一个分配问题： http://en.wikipedia.org/wiki/Assignment_problem 。


这可以解决使用匈牙利算法： http://en.wikipedia.org/wiki/Hungarian_algorithm


在您的情况下，您的成本是不快乐。并且你可以使用该算法找到能给你最少不快乐的组合。在多项式时间。

What you have is called an assignment problem: http://en.wikipedia.org/wiki/Assignment_problem.

And that can be solved using the Hungarian Algorithm: http://en.wikipedia.org/wiki/Hungarian_algorithm

In your situation, your cost is "unhappiness" and you can use the algorithm to find the combination that will give you the least "unhappiness" in polynomial time.

我没有看到任何方式评论你的答案，所以我写的是''回复''。这个算法非常好，但我的问题有点复杂。医管局的假设是我们有n个人和n个工作。我有k个工作，其中k> = n。更重要的是，一项工作要完全由指定数量的人完成，所以我不能只复制工人，因为一个工人将多次被选为一个工作......

I do not see any way to comment Your answer, so I am writing as a ''reply''. This algorithm is very nice, but my problem is a little bit more complicated. The assumption in HA is that we have n people and n jobs. I have k jobs, where k >= n. What is more, one job is to be done exactly by specified number of people, so I cannot just duplicate workers, because one worker would be selected for one job multiple times...

也许你需要提供一个例子，因为我没有看到使用算法有任何问题。您所要做的就是首先在n个作业上使用算法。然后在剩余的k-n个作业上再次使用该算法。

Perhaps you need to provide an example because I don''t see any problem with using the algorithm. All you do is first use the algorithm on n jobs. Then use the algorithm again on the remaining k - n jobs.

这篇关于找到最大幸福总和的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！