两个执行者共享作业的算法 [英] Algorithm for sharing jobs by two executors

问题描述

我在测试一些网站时遇到了以下问题:

I encountered the following problem, while testing some web-site:

约翰和玛丽创办了 J&M 出版社并购买了两台旧打印机装备它.现在他们有了第一笔商业交易——打印一张包含 N 页的文档.打印机似乎工作在不同的速度.一个在 X 秒内生成一个页面，另一个在 X 秒内生成一个页面Y 秒.所以现在公司创始人对他们的最短时间感到好奇可以用两台打印机打印整个文档.

John and Mary founded J&M publishing house and bought two old printers to equip it. Now they have their first commercial deal - to print a document consisting of N pages. It appears that printers work at different speed. One produces a page in X seconds and other does it in Y seconds. So now company founders are curious about minimum time they can spend on printing the whole document with two printers.

(取自这里 http://codeabbey.com/index/task_view/two-printers)

我认为这是贪心算法的问题，但据说 N 可能高达十亿，所以也许有一些我看不到的更简单的解决方案.我能否找到解决方案，以某种方式将它们与 X 和 Y 成比例?

I thought it is the problem for greedy algorithm, but it is told that N could be up to billion, so there perhaps is some simpler solution which I could not see. Could I come to solution dividing them in proportion to X and Y somehow?

推荐答案

这似乎是一道数学题，而不是算法题.作业分配将是 YN/(X+Y) 页到 X，XN/(X+Y) 页到 Y.总时间将是 XYN/(X+Y)，这是最优的(注意它等价于 N/(1/X + 1/Y).因为 >YN/(X+Y) 可能不是整数，你可以只计算几个值(如果 X 向上取整，Y 向下取整，反之亦然)，然后取最小值.或者如您所说，您可以将两者舍入并将任何剩余的工作分配给速度更快的机器.

This seems to be a math question rather than algorithm question. The job distribution would be YN/(X+Y) pages to X, XN/(X+Y) pages to Y. Total time would be XYN/(X+Y) which is optimal (note that it is equivalent to N/(1/X + 1/Y). Since YN/(X+Y) might not be integer, you can just calculate a few values (if X is rounded up and Y is rounded down, and vice versa) , then take the minimum. Or as you said, you can round down both and give any remaining jobs to the faster machine.

这篇关于两个执行者共享作业的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！