m**q
发帖数: 189 | 1 题目6. 任务分配，假设有N个任务，每个任务需要W_i工作量，M个人，每人每天能做工
作量w_i，如何安排工作，使得所有工作能最快完成。这个问题其实更像一个开放性问
题，因为一个合理的贪心策略，最后的结果跟最优结是很接近的(大致上，最多只差一
天)。
是小尾羊以前提到的题目，可能是老题了，没找到答案。
求解答 |
B*******1
发帖数: 2454 | |
i**d
发帖数: 357 | 3 不一样，1337code的题目是每个人必须做连续的job.
而这里没有这个限制，按道理来说，这道题的难度更大一些。
【在 B*******1 的大作中提到】
: 我哪里理解错了，这题跟这题有什么区别啊？
: http://www.leetcode.com/2011/04/the-painters-partition-problem-
|
C***U
发帖数: 2406 | 4 I think we can use greedy algorithm, as you said
【在 m**q 的大作中提到】
: 题目6. 任务分配，假设有N个任务，每个任务需要W_i工作量，M个人，每人每天能做工
: 作量w_i，如何安排工作，使得所有工作能最快完成。这个问题其实更像一个开放性问
: 题，因为一个合理的贪心策略，最后的结果跟最优结是很接近的(大致上，最多只差一
: 天)。
: 是小尾羊以前提到的题目，可能是老题了，没找到答案。
: 求解答
|
m**q
发帖数: 189 | 5 嗯，1337coder的题目有两个assumption
1. 每个人必须做连续的job
2. 每个人工作效率相同
在这题里面都不满足
【在 i**d 的大作中提到】
: 不一样，1337code的题目是每个人必须做连续的job.
: 而这里没有这个限制，按道理来说，这道题的难度更大一些。
|
m**q
发帖数: 189 | 6 关键是如何贪心才能保证距离最优结果大致只差一天呢
【在 C***U 的大作中提到】
: I think we can use greedy algorithm, as you said
|
