Problem
Suppose we have a set of N real numbers A = {x_1, x_2, ..., x_N}.
The goal is to partition this set into A_1, A_2, ..., A_L subsets with the limitation of sum( A_i ) <= T and minimizing this term:
Cost := sum( abs( sum(A_i) - T ) )
where sum(A_i) denotes the summation of numbers in A_i and T is a given threshold.
I am looking for a non-evolutionary optimal algorithm.
Update: x_i are real positive numbers and not greater than T ( 0 < x_i <= T ).
Update 2: The cost function fixed.
Nice try, Greedy algorithm!
A simple idea is to use a Greedy approach to solve the problem. Here is a pseudocode:
1. create subset A_1 and set i=1.
2. remove the largest number x from A.
3. If sum(A_i) + x <= T
* put x into A_i
4. Else
* create a new subset A_i+1,
* put x into A_i+1
* set i=i+1
5. If A is non-empty
* goto step 2.
6. Else
* return all created A_i s
The problem is this solution is not optimal. For example, there are cases that it is better not to put two largest numbers, x1 and x2, in the first subset A_1 even they don't exceed T, because there is no other *x_i* available to add to that set and make its sum closer to T. In the other hand, if we had put x1 and x2 in the separate sets, a better solution could be found (a solution with smaller Cost value).
Possible solutions
I have thought of using a Backtracking algorithm which can find the optimal solution too, but I guess its complexity in this problem would be high.
I have read some article on Wikipedia like Bin packing problem (NP-hard [sighs...]) and Cutting stock problem and apparently my problem is very similar to this standard problems, but I am not sure which one matches my case.
Update: With the corrected cost function, note that sum(A_i) - T will always be negative as A_i <= T. So our objective is to minimize
sum(abs(sum(A_i)-T)) = sum(T-sum(A_i)) = L*T-sum(A)
sum(A) is constant, so the task is to minimize the number of used bins. Therefore your problem is equivalent to classic bin packing.
For solving this you could use a bin packing solver like this one.