遞歸與一維數組

Question

我一直盯着這個問題幾個小時。出於某種原因，我理解洪水填充和二維陣列遞歸，但似乎無法開始在這個問題上：

你有三個助理爲你工作。一個叫傑夫，另一個叫傑夫，第三個叫傑夫。它們都以每分鐘一頁的速度打印。你今天帶着一大堆你需要儘快輸入的文件來到你的辦公室。你必須將這些文件分發給你的助手，以便他們儘早完成所有文件。 「傑夫做到了，」你大叫。 「傑夫那樣做，」你說。 「傑夫，完成這項工作，」你警告。所以傑夫做到了。但你需要幫助他。所以你有這個APT。

你的任務是給定一個int []和每張紙的頁數，返回你的助手鍵入所有這些紙張所需的最少分鐘數。假設他們不能將一張紙分成幾部分，即每張紙由一個人打印。例如，給定{1,2,3,4,5,6,7}，函數應返回10，因爲7 + 3 = 10,6 + 2 + 1 = 9和5 + 4 = 9（還有這些數字的其他組合將產生相同的結果）。

Answer 1

你的任務基本上是解決分區問題。

https://en.wikipedia.org/wiki/Partition_problem

因爲這個任務是NP完全問題，不能在多項式時間內解決（最佳）。解決方案只能近似。

最簡單的apprach將是貪心算法：

首先，你在降序排序表。之後，您可以遍歷它，將任務分配給目前爲止分配工作量最少的Jeffs。

無需遞歸。