1

Given a multiset of n positive integers partition them into 17 parts such that the maximum sum of the parts is minimized.

I need the algorithm for the above question in time polynomial in n and M, where M is the maximum element in the multiset. I have tried DP and would love to know if there is a DP algo which can solve this efficiently

3
  • possibly a duplicate of stackoverflow.com/questions/6454598/… with k = 17. The runtime of the DP algorithm is O(n x M x k).
    – Faraz
    Feb 26, 2013 at 1:45
  • But there is a fundamental difference as in the above question reordering of numbers is prohibited but not in my question
    – 1234
    Mar 3, 2013 at 11:15
  • This question allows us to reorder the elements. I think it is difficult than the question referred in above comment.
    – Swapniel
    Sep 30, 2014 at 13:48

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.