1

Say we have a number sequence, and we have X sections to divide this into:

1, 4, 7, 9, 3, 11, 10

If we had 3 sections, the optimal answer would be:

[1, 4, 7][9, 3][11, 10] or [1, 4, 7, 9][3, 11][10]

Since the largest sum = 21. This is the best case. (I think, I did it by hand).

We want each section to be as equal as possible. How can this be done? My first attempt at an algorithm was to find the highest X values (9, 11, 10), and base the regions off of that. That does not work in an example like below, since one of the regions will NOT contain one of the highest values in the set:

3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1,

Again with X=3 sections, optimal answer:

[3, 2][2, 1, 1, 1][1, 1, 1, 1, 1]

Of course I could brute force every possible combination, but there is a much more efficient way of doing this. But I'm having trouble finding it.

user1472747
  • 529
  • 3
  • 10
  • 25
  • This sounds like the [Linear Partition problem](http://avdongre.wordpress.com/2011/07/12/the-partition-problem/). Here's a [solution](http://coliru.stacked-crooked.com/a/051e017401df0353). –  Mar 08 '14 at 03:08

3 Answers3

1

This is exactly the linear partition problem as @rta3tayt32yaa32y says.

If you really mean a greedy algorithm as your subject says, which will be an approximation, then just divide the sum of elements by X. Call this D. Maintain an accumulated sum as you work from beginning to end of the list. Every time the sum reaches D or more, make the previous elements a section, delete them, and restart the sum. If the sequence is 1, 4, 7, 9, 3, 11, 10, the sum is 45. For X=3, we have D=15. So the first section is [1, 4, 7] because adding 9 would make the sum 21. The next is [9, 3] because adding 11 would make the sum 22. This leaves [11,10] for the last.

To find the exact answer, you need a dynamic program. This has already been extensively discussed here so I won't repeat that. The question is rather confused, but the answer of @Óscar López is very good.

Community
  • 1
  • 1
Gene
  • 46,253
  • 4
  • 58
  • 96
0

I would try to first start by grouping all the numbers into subgroups of equal size rather than sum. Now you can go through and poll all these subgroups' sums, and calculate the average subgroup sum. You should now iterate through each subgroup and perform the following manipulations to the subgroup:

If the subgroup's sum is LESS than the average AND the sum of subgroup to its right is GREATER than average, check if one element from the right subgroup can be moved to the left subgroup. (I'll elaborate on 'checking' later) If the subgroup's sum is LESS than the average and the sum of subgroup to its right is LESS than average, do nothing and move on to the next subgroup If the subgroup's sum is GREATER than the average and the sum of subgroup to its right is LESS than average, check if one element from the subgroup can be moved to the subgroup on its right. If the subgroup's sum is GREATER than the average and the sum of subgroup to its right is also GREATER than average, do nothing and move on to the next subgroup.

What do I mean by 'check' if you can move an element? An element should only be moved if this movement will bring the element's destination-subgroup closer to the average than it will move the source-subgroup. So if an element movement from left to right subgroup brings the right subgroup 3 closer to the average, it should NOT result in the left subgroup becoming further from the average by 3 or more. Also, obviously an element should only be moved as long as there is still at least one element left in its source subgroup.

Were not done though. So when you've gone through all the subgroups and made any element movements, you should then go back through and once again get the sums of all the subgroups and find the new average. Now you start over, going through the subgroups and making movements which bring them closer to this new average. Once you are able to go through all the subgroups and find that no movements were able to be made, you are done.

NOTE: This might not work, I haven't tested it, its just an idea I have Hope it helps.

stackPusher
  • 6,076
  • 3
  • 35
  • 36
0

The solution for this problem is not greedy as you stated in your question title. It is in fact a dynamic programming one. In particular, it is the classic partition problem, related with the better known knapsack problem, which is often confused as having a greedy solution (but it doesn't).

If the classic knapsack problem tries to fit in (the best) objects that have a total S, read as input. In your case, you just need to fit some objects that add up to volume T/p to obtain the first partition (where T here is the total of the numbers in your array and p is the number of partitions). This will generate a partition whose sum is as close as possible to T/p. The only solution that comes to mind to generate the rest of the partitions is to eliminate the numbers used so far and re-iterate for p-1 partitions. So, I would use something like this:

while (p>=2) {
   partition = getSet(knapsack(v,T/p));
   v.removeAll(partition);
}

For knapsack implementations, just use google... there's more than enough already existing implementations in all sorts of languages.

Catalin Pol
  • 261
  • 1
  • 3