Need an idea to solve this puzzle algorithm

Question

I have encountered some similar problems with this in the past, and I still don't have a good idea how to solve this problem. The problem is as follows:

You are assigned an integer array with size n <= 1000 and k <= n, which is the number of adjacent subarrays that you need to split into your array. You should print the minimum m, where m = max {s [1], ..., s [k]}, and s [i] is the sum of the ith subarray. All integers in the array are between 1 and 100. Example:

Input: Output: 5 3 >> n = 5 k = 3 3 2 1 1 2 3 

Division of an array into 2 + 1 | 1 + 2 | 3 minimizes m.

My brute force idea was to make the first subarray end at position i (for all possible i), and then try to split the rest of the array in k-1 subarrays in the best way. However, this is an exponential solution and will never work.

So, I am looking for good ideas to solve it. If you have one, tell me.

Thank you for your help.

Answer 1

You can use dynamic programming to solve this problem, but in fact you can solve it with a greedy and binary search for an answer. This complexity of the algorithm is O(n log d) , where d is the output answer. (The upper bound will be the sum of all the elements in the array.) (Or O( nd ) in the size of the output bits)

The idea is to binary search your test m , and then eagerly move forward through the array, adding the current element to the section, unless adding the current element pushes it along the current m - in this case you start a new section. The current m is successful (and thus corrects your upper bound) if the numbers of the section used are less than or equal to your given input k . Otherwise, you have used too many partitions and raised your lower bound by m .

Some pseudo codes:

 // binary search binary_search ( array, N, k ) { lower = max( array ), upper = sum( array ) while lower < upper { mid = ( lower + upper ) / 2 // if the greedy is good if partitions( array, mid ) <= k upper = mid else lower = mid } } partitions( array, m ) { count = 0 running_sum = 0 for x in array { if running_sum + x > m running_sum = 0 count++ running_sum += x } if running_sum > 0 count++ return count } 

It should be easier to come up conceptually. Also note that due to the monotonicity of the partition function, you can actually skip the binary search and perform a linear search if you are sure that the output of d not too large:

  for i = 0 to infinity if partitions( array, i ) <= k return i 

Answer 2

Dynamic programming. Make an array

 int best[k+1][n+1]; 

where best[i][j] is the best that can be achieved by breaking the first j elements of the int i subarrays array. best[1][j] is just the sum of the first elements of j . Having row i , you calculate row i+1 as follows:

 for(j = i+1; j <= n; ++j){ temp = min(best[i][i], arraysum[i+1 .. j]); for(h = i+1; h < j; ++h){ if (min(best[i][h], arraysum[h+1 .. j]) < temp){ temp = min(best[i][h], arraysum[h+1 .. j]); } } best[i+1][j] = temp; } 

best[m][n] will contain the solution. Algorithm O (n ^ 2 * k), maybe something better.

Edit: a combination of the ideas of ChingPing, toto2, Coffee on Mars and rds (in the order in which they appear when I see this page at the moment).

Set A = ceiling(sum/k) . This is a minimum minimum estimate. To find a good upper bound for a minimum, create a good section in any of the above ways, moving the borders until you find some simple move that will reduce the maximum dose anyway. This gives you an upper bound B, not much larger than a lower bound (if it were much larger, you would have found a slight improvement by moving the bound, I think). Now let's start the ChingPing algorithm, with a known upper bound, reducing the number of possible branches. This last phase is O ((BA) * n), finding B unknown, but I think it is better than O (n ^ 2).

Answer 3

I have a sucking branch and a related algorithm (please don't scale me down)

First, take the sum of the array and dvide by k, which will give you the best case associated with you, for example, average A. We will also keep the best solution that is still considered for any GO branch (global optimal). Let's look at we put a separator (logical) as a block of sections after some element of the array, and we need to put the sections k-1. Now we will post sections with greed in such a way

Rotate the elements of the array, summing them until you see that at the next position we will exceed A, now we will make two branches where you put the separator at this position and the other where you put the next position, do it recursively and set GO = min (GO, answer for the branch). If at any point of any branch we have a partition greater than GO, or no position less, then the sections remaining in order to be tied. In the end, you must be GO when you answer.

EDIT: As Daniel suggested, we could slightly change the placement strategy for the separators until you reach the sum of the elements, since A or the remaining positions remain smaller than the separators.

Answer 4

This is just a sketch of an idea ... I'm not sure if it works, but it is very simple (and probably also fast).

You start talking, dividing evenly distributed (it really doesn't matter how you start).

Make the sum of each subarray. Find the Subaru with the highest amount. Look at the right and left adjacent subarrays and move the division on the left by one if the subframe on the left has a lower sum than the one on the right (and vice versa). Repeat for the machine with the current largest amount.

You will encounter some situation where you will continue to break away from the separation between the same two positions, which probably mean that you have a solution.

EDIT : see comment from @rds. You will have to think more about bouncing solutions and the final conditions.

Answer 5

If your array has random numbers, you can hope that the section in which each subarray has n / k is a good starting point.

From there

• Rate this candidate decision by calculating the amounts
• Save this candidate decision. For instance:
  • array of indices of all subarrays
  • corresponding maximum amount for sub-matrices
• Reduce size max. sub-array: create two new candidates: one with a sub-array starting at index + 1; one with a sub-array ending in index-1
• Rate new candidates.
  • If their maximum is higher, cancel
  • If their maximum value is less, repeat iteration by 2, except that this candidate has already been evaluated, in which case this solution.

Answer 6

My idea, which unfortunately does not work:

• Split an array in N subarrays
• Find the two adjacent subarrays whose smallest sum
• Merge the subarrays found in step 2 to form a new continuous subarray
• If the total number of subarrays is greater than k, repeat the operation from step 2, otherwise finish.