dynamic programming - Divide an array into k or less subparts to minimize the maximum sum of each part -

i need divide array k or less subparts minimize maximum sum of each part.

for example array has elements: 5,10,21,20

if k=2, array can divided in 2 sub-arrays: {5,10,21} , {20}. have return maximum sum of subarray (36 in above example).

when k>=4, answer largest element of array.

also, order in array elements chosen cannot changed, can't sort array , proceed.

you use greedy solution if want good-enough solution:

def minmax(lst, k):     lst = sorted(lst, reverse=true)  # biggest numbers first better     subs = [[] _ in xrange(k)]   # create lists subarrays      while lst:         subs[0].append(lst.pop(0))         # append 1 lowest sum         subs.sort(key=sum)                 # sort sum (lowest first)         print subs                   # print subarrays while creating them      return sum(subs[-1])    # have sorted sums, last has biggest sum 

this not guarantee produce best result, works pretty well.

k = 2

this example:

print 'result %d' % minmax([5, 10, 21, 20], 2) 

output

[[], [21]] [[20], [21]] [[21], [20, 10]] [[21, 5], [20, 10]] result 30 

well, found better solution 1 showed.

k >= 4

let's try k=4 , k=5

>>> print 'result %d' % minmax([5, 10, 21, 20], 4) [[], [], [], [21]] [[], [], [20], [21]] [[], [10], [20], [21]] [[5], [10], [20], [21]] result 21  >>> print 'result %d' % minmax([5, 10, 21, 20], 5) [[], [], [], [], [21]] [[], [], [], [20], [21]] [[], [], [10], [20], [21]] [[], [5], [10], [20], [21]] result 21 

you add code beginning of function directly return max of lst when k >= len(lst):

def minmax(lst, k):     if k >= len(lst):         return max(lst)     .... 

minimum makespan problem

this type of problem famous name of minimum makespan problem, searching retrieve lots of information algorithms guaranteed produce optimal result, explanation far complex stack overflow answer, while greedy 1 fun , instructive.