Distribution of numbers - Hard one

[Wizzuriz]

Hello all,

 

I would like to hear if there is someone here that can help me figure out how to do this.

 

I have an array with some values in example:  array(7.50, 9, 4.50, 6.50, 3.75); now I would like to distribute them to 3 other arrays and get the values in each of the new arrays so close to the average of the first array values.

 

I get the average to 10.416666666667 so a cool result could be: array_1(9), array_2(4.5, 6.50) & array_3(7.50, 3.75).

 

I really don't know how to do this.

 

Please let me know if you have an idea on how to solve this.

 

Best regards

Wizzuriz

 

 

 

[Barand]

I am curious about how you get an average that is greater than all the values in the array

[requinix]

He calculated the "average" to be over the number of arrays, not the number of inputs.

 

(7.50 + 9 + 4.50 + 6.50 + 3.75) / 3 arrays = ~10.42 per array

[davidannis]

Looks like this is a very hard problem that short of a brute force algorithm can not be definitively solved.

http://en.wikipedia.org/wiki/3-partition_problem

Pseudocode for an approximation of the optimal solution for dividing into two arrays (the greedy algorithm) that you could adapt to an n array solution is available here. http://en.wikipedia.org/wiki/Partition_problem

[Wizzuriz]

Looks like this is a very hard problem that short of a brute force algorithm can not be definitively solved.

http://en.wikipedia.org/wiki/3-partition_problem

Pseudocode for an approximation of the optimal solution for dividing into two arrays (the greedy algorithm) that you could adapt to an n array solution is available here. http://en.wikipedia.org/wiki/Partition_problem

 

Thanks for the post, very nice stuff.

 

I don't need it to be definitively solved, I just need to distribute the values from the main array into 3 other arrays with a sum near the average.

Example.

 

Main_Array(7.50, 9, 4.50, 6.50, 3.75) solved into array_1(7.50,3.75) array_2(9)array_3(6.50,4.50) The sum don't need to be 100 match just evenly distributed +/- some value.  

 

If you have an example of some php code with a method to solved this please let me know.

 

Best regards

Wizzuriz

[Barand]

A point of clarification -

 

Is the problem to distribute 5 values over 3 arrays?

or

Is the problem more general to distribute P values over Q arrays?

[Wizzuriz]

A point of clarification -

 

Is the problem to distribute 5 values over 3 arrays?

or

Is the problem more general to distribute P values over Q arrays?

The problem is to distribute P values over Q arrays.

 

Now with the numbers in the example we can't distribute them 100 evenly so the goal is to distribute them as evenly as possible.

 

* WIzzuriz

[davidannis]

WIzzuriz,

 

I'm pretty sure this is a homework assignment and not an easy one. If you take a stab at it using the any of the pseudocode algorithms I pointed you to i'll help debug and improve it, but I won't write it for you.