k partition algorithm - divide work load equally between k workers

Question

I once read a problem in my Introduction to Algorithms (MIT Press) book which stated.

We have a book with 100 pages and each page has a weight associated with it equal to its page number therefore the weights are i.e. 1,2,3,4,5. These weights represent the difficulty of the page in translation to other language. We have K people assigned the work of translating the pages in another language but we have to divide the work load such that they have almost equal amount of work.

So if we have 5 pages i.e 1,2,3,4,5 and K=3 then k1=2+3=5, k2=1+4=5 and k3=5

Do you have online reference to this problem because I can't find it on google? OR Do you know the name of this algorithm?

Answer 1

This looks like an instance of the first fit descending algorithm to me.

Answer 2

Its a variation of Knapsack Problem :)

Thanks

Answer 3

That's known as First Fit Descending or First Fit Decreasing, or sometimes the bin packing algorithm, as it's used for efficiently packing objects into containers or for cutting pieces of a material into smaller components.

There's a nice implementation for Perl in the module Algorithm::BinPack.

Answer 4

Special Case: I Just thought this could be interesting

Reminds me of the story of Gauss in elementary school...

No need for anything fancy, a translator will get two pages at a time,

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

So we split 50 pages between the translators (any order would do), they would also get the 101-x th page with the x page.

pseudo-code:

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

note: if n were odd, or if n/2 were not divisible by j, the work won't be fairly divided between the translators - this works perfectly in case n=100 and k in (1,2,5,10,25,50).

Answer 5

Its called Linear Partition problem

The problem and solution both are at http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM