问一道G家题

laiguojiuhao 发表于 2017-1-14 04:32
我是看到原帖作者是每次做最长时间的工作，既然他拿了offer我就假设他没问题；感觉有个条件可能，要不然 ...

分析的很有道理啊。。 这么一想这题好难啊。 那按照你这么思路， 有一个general的最佳策略么，我是说选工作的策略

小A要当码农 发表于 2017-1-14 04:52
分析的很有道理啊。。 这么一想这题好难啊。 那按照你这么思路， 有一个general的最佳策略么，我是说选工 ...

没有。。。不过感觉似乎有一点道理，就是如果工人数固定，那可以用贪心从最大的开始安排；如果之后不再造人，这就是最优的；如果之后又造了人，那么根据我们的递归算法肯定会有一个分支是先造了同样数量的人然后开始贪心地安排工作，似乎能够cover到。比如我之前的长中短的例子，那么会有一个分支先造人，然后长中，中的完了再短，总共造一个人的情况下是最优的。
证明不会

laiguojiuhao 发表于 2017-1-14 05:52
没有。。。不过感觉似乎有一点道理，就是如果工人数固定，那可以用贪心从最大的开始安排；如果之后不再造 ...

感觉只能暴力做。。。而且比原先假想的暴力还要再多一层（遍历job的顺序。。。）

首先二分查找要多少个人
然后问题变成n个job，k个人，怎么分配最快完成。这个问题有办法解吗？

fengyang0317 发表于 2017-1-14 07:20
首先二分查找要多少个人
然后问题变成n个job，k个人，怎么分配最快完成。这个问题有办法解吗？

二分查找要多少个人是什么意思？

np hard问题吧，比如简化问题，有k个人n个job分配，这个简化都的问题就是NP hard..感觉没啥方法去做

有点不明白，同一个任务是只能由一个工人做还是可以多个工人并行做呢？

小A要当码农 发表于 2017-1-14 07:25
二分查找要多少个人是什么意思？

想简化成16楼说的问题。

最后总共用了k个人，k从1到n变化，我猜用的时间是先减少后增加，也可能只增加或者只减少。

不知道这样猜成立不成立。

如果成立，而且16楼说的问题可以解，就可以用三分来确定k。

zxj1987 发表于 2017-1-14 08:41
np hard问题吧，比如简化问题，有k个人n个job分配，这个简化都的问题就是NP hard..感觉没啥方法去做

01背包就是NP的，如果总的重量不是太大，用动态规划也能解。

这个job分配的问题也有希望能解吧

laiguojiuhao 发表于 2017-1-10 07:47
每个工作应该只能一个做，搜索的上限是工人数量等于待完成的工作数量吧，再多没意义；简单的模拟可以设计一 ...

刚刚又想了一下这个题， 思路和你这个是一样的。 假设原帖作者说的每次挑选工作优先挑时间最长的话， 还需要维护一个关于job的max heap。 这样的话似乎可以根据当前闲置工人数目和当天剩余工作数目（因为挑选策略的原因，每次我们遇到还剩N个工作的case，这N个工作一定是一样的（最短的N个））做memo...