算法由兩個遺囑執行人

共享工作我遇到以下問題，同時測試一些網址：算法由兩個遺囑執行人

約翰和瑪麗成立Ĵ&中號出版社買了兩張舊打印機裝備它。現在他們有了第一個商業交易 - 打印由N頁組成的文檔。看來，打印機在不同的速度工作。一個在X秒內產生一個頁面，另一個在 Y秒內產生一個頁面。所以現在公司的創始人對於他們花費在用兩臺打印機打印整個文檔上的最短時間很感興趣。

我認爲這是貪心算法的問題，但被告知N個可能高達十億，所以有可能是一些簡單的解決方案，我看不出（從這裏http://codeabbey.com/index/task_view/two-printers拍攝）。我能不能解決它們與X和Y成比例的問題？

來源

2013-10-04 Alumashka

這似乎是一個數學問題而不是算法問題，工作分配是'YN /（X + Y ）''到'X'，'XN /（X + Y）'頁面到'Y'，總時間將是'XYN /（X + Y）'，這是最優的（注意它相當於'N /由於'YN /（X + Y）'可能不是整數，所以可以計算一些值（如果'X'被四捨五入並且'Y'被舍入，相反），然後取最小值。 – justhalf

哦，我現在看到了！肯定來到相同的公式，但我沒有發明如何處理整數結果。多虧了你，這變得很清楚：我需要將他們兩人都輪換下來，然後只剩下一份工作，應該由貪婪原則來分配。看起來這可能是推斷K隊列......再次感謝！ – Alumashka

我已經回答了你的問題，如果你可以upvote並接受我的回答，我會非常感激^^ – justhalf

這似乎是一個數學問題，而不是算法問題。工作分配將爲YN/(X+Y)頁至X,XN/(X+Y)頁至Y。總時間應該是XYN/(X+Y)這是最優的（注意它相當於N/(1/X + 1/Y)。因爲YN/(X+Y)可能不是整數，所以可以計算一些值（如果X被四捨五入，Y向下舍入，反之亦然），然後取或者像你說的那樣，你可以將兩者都舍入並且給任何剩餘的工作提供更快的機器

來源

2013-10-04 08:47:31 justhalf

算法由兩個遺囑執行人

回答

相關問題