ķ分區算法 - K工人之間的鴻溝工作負載同樣

我曾經在我的算法導論（麻省理工學院出版社）一書，其中指出讀取的問題。ķ分區算法 - K工人之間的鴻溝工作負載同樣

我們有一本100頁，每頁都有一個與之關聯等於其頁碼因此權重，即1,2,3,4,5的重量。這些權重代表翻譯爲其他語言的頁面的難度。我們有K個人分配翻譯另一種語言的頁面的工作，但我們必須分配工作量，使他們的工作量幾乎相等。

因此，如果我們有5頁，即1,2,3,4,5和K = 3，則K1 = 2 + 3 = 5，K2 = 1 + 4 = 5和K3 = 5

你有網上參考這個問題，因爲我無法在谷歌上找到它？或你知道這個算法的名字嗎？

這是書上的紅色移動封面？我喜歡那本書;很高興聽到它仍在使用。 – Ether 2009-12-12 17:55:03

@Ether：我還沒有看到它上面有一個紅色的移動設備，至少它沒有放在我用過的書的封面上:)，可能在舊版本中！ – 2009-12-12 17:58:44

http://mitpress.mit.edu/algorithms/ – Ether 2009-12-12 18:01:28

這看起來像第一嵌入下降算法，我的一個實例。

2009-12-12 17:48:41

這稱爲第一擬合降序或首先擬合降低，或者有時裝箱算法，因爲它是用於高效地包裝物體插入容器或用於切割材料的片成較小的部件。

有模塊Algorithm::BinPack在一個不錯的實現爲Perl。

2009-12-12 17:57:46 Ether

但在這種情況下，垃圾桶的尺寸是多少？工人的工作量沒有限制。 – 2013-06-02 15:45:53

我想你可以用最小的總和將每個項目添加到bin中，但是第一個適合遞減算法仍然只是一個近似算法，所以它不會總是返回最優解。 – 2013-06-02 16:35:49

特例：我只是認爲這可能是有趣的

讓我想起了高斯在小學的故事......

無需任何幻想，翻譯會得到在同一時間兩頁，

1+100=101 
2+99=101 
... 
50+51=101

因此，我們的翻譯之間的分裂50頁（任意順序會做），他們也會得到第x頁的第101頁。

僞代碼：

n=100 // 100 pages 
k=5 // 5 translator 
for i=1 to n/2 
    print "Translator " ,(i mod k) +1, "gets pages", i , " and " , n-i+1

注：如果n是奇數，或者如果n/2不整除用j，工作不會得到公平的翻譯者之間的分成 - 這工作完全的情況下，（1,2,5,10,25,50）中n = 100和k。

2009-12-22 07:32:58

哦。每當有人提出NP難題時，我的算法教授總是會講這個故事。 – 2010-05-16 20:15:52

回答