0
$\begingroup$

I have M numbers arranged into a line. I need to divide the line into N groups without changing numbers order such that the sums of the numbers of each group are closest to the mean of these sums by absolute differences.

Example:

Numbers: 1 2 3 4 5 6 7 8 9 10, need to divide into 3 groups.
Let's say we want to minimize sum of absolute differences (SAD).
Groups: (1) 1 2 3 4 5 6 (sum = 21); (2) 7 8 (sum = 15); (3) 9 10 (sum = 19)
Mean = (21+15+19)/3 = 18.33, SAD = 21-18.33 + 18.33-15 + 19-18.33 = 6.67 <- That's what we want to minimize.

The question is how to solve it using dynamic programming?


The original question - https://stackoverflow.com/questions/9275280

$\endgroup$
  • 1
    $\begingroup$ What have you tried so far? What happens when you have 1 number and $n > 1$ groups? What happens when you have 2 numbers and $n > 2$ groups? What happens when you have $n$ numbers and $n$ groups? What happens when you have $k$ numbers and $n = 1$ groups? Think about these, because these will be you base cases. If we have optimally solved this problem for $n-1$ groups, how can we use this information to solve it for $n$ groups? $\endgroup$ – ryan Apr 9 '19 at 19:56
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Apr 9 '19 at 21:19
  • $\begingroup$ Nice question. It looks like none of the answers at the original question uses dynamic-programming. All of them are likely to run much slower than a proper solution by dynamic-programming when 𝑁 becomes larger. $\endgroup$ – John L. Apr 10 '19 at 1:20
0
$\begingroup$

Fortunately you can calculate the group average that you are aiming for (sum of numbers, divided by the number of groups). In your case, you want the groups close to 18 1/3.

So using dynamic programming, you solve "How do I split the first m numbers into n groups, minimizing abs (sum of numbers in group - 18 1/3)", for 0 ≤ m ≤ M, and for 1 ≤ n ≤ N. You solve this by putting 0 ≤ k ≤ m items in the last group, calculating the penalty for the last group and adding the solution for n-1 groups made from the first m-k items, picking the best choice.

It feels a bit weird, because the solutions you find on the way are awfully bad. Splitting the first 0 numbers for example into 3 groups creates 3 empty groups, with a total sum of 3 * (18 1/3) = 55, but it works. What you find for N groups from M numbers is optimal.

This works easily on O (M^2 N). You can do this faster by first finding a reasonably good solution, and then excluding everything that isn't as good as the best solution.

Example: First, make each group as large as possible without the first n groups exceeding n * 18 1/3, that is (1 2 3 4 5) (6 7 8) (9 10) with penalties 3 1/3, 2 2/3, 2/3, total 6 2/3. Now we only care for 1 group with a penalty ≤ 6 2/3, then for 2 groups with a penalty ≤ 6 2/3 etc.

But also, if the remaining M-m items that need to go into N-n groups have a sum of S, they must have a penalty of at least abs (S - 18 2/3 * (N - n)), so the penalty for the first n groups plus this extra penalty must be ≤ 6 2/3. This will help if you have thousands of items.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.