How can I split an array of numbers into two batches?
I have an array of numbers (the following is an example):
261,380.00
217,940.00
157,160.00
245,460.00
253,420.00
128,160.00
467,720.00
128,160.00
245,460.00
128,160.00
245,460.00
245,460.00
128,160.00
Total = 2,852,100.00
1) I would like to know how can I determine whether the array can be split into two, such that the sum for each of two batches is less than 1,430,000.00.
2) If the sum can be split into two batches, how can I determine which numbers go into batch 1 and which numbers go to batch 2.
3) Since the numbers can vary, is there any algorithm that can determine the answer for question 1 and 2 above, provided that the total sum of all numbers is less than 2,860,000.00.
Thank you.
261,380.00
217,940.00
157,160.00
245,460.00
253,420.00
128,160.00
467,720.00
128,160.00
245,460.00
128,160.00
245,460.00
245,460.00
128,160.00
Total = 2,852,100.00
1) I would like to know how can I determine whether the array can be split into two, such that the sum for each of two batches is less than 1,430,000.00.
2) If the sum can be split into two batches, how can I determine which numbers go into batch 1 and which numbers go to batch 2.
3) Since the numbers can vary, is there any algorithm that can determine the answer for question 1 and 2 above, provided that the total sum of all numbers is less than 2,860,000.00.
Thank you.
ASKER
Hi ozo,
Sorry to say that I am not good at algorithm. I just read the link in your post and tried using the sample values. For greedy algorithm, one of the batch exceeds a little bit over 1,430,000. For differencing algorithm, I don't fully understand how it works.
May I seek your help to explain "approximating the numbers by removing a factor of 143000000*2-285210000 and then applying a pseudo-polynomial time algorithm"?
Thank you.
Sorry to say that I am not good at algorithm. I just read the link in your post and tried using the sample values. For greedy algorithm, one of the batch exceeds a little bit over 1,430,000. For differencing algorithm, I don't fully understand how it works.
May I seek your help to explain "approximating the numbers by removing a factor of 143000000*2-285210000 and then applying a pseudo-polynomial time algorithm"?
Thank you.
SOLUTION
membership
Create a free account to see this answer
Signing up is free and takes 30 seconds. No credit card required.
ASKER
It seems that as the number of my data set is 13 (which is fixed), the differencing algorithm cannot be used. Am I right?
SOLUTION
membership
Create a free account to see this answer
Signing up is free and takes 30 seconds. No credit card required.
SOLUTION
membership
Create a free account to see this answer
Signing up is free and takes 30 seconds. No credit card required.
ASKER CERTIFIED SOLUTION
membership
Create a free account to see this answer
Signing up is free and takes 30 seconds. No credit card required.
SOLUTION
membership
Create a free account to see this answer
Signing up is free and takes 30 seconds. No credit card required.
http://en.wikipedia.org/wiki/Partition_problem#Approximation_algorithm_approaches
The partition problem is NP complete, but there is a pseudo-polynomial time algorithm that runs in O(N*n), where n is the number of elements in the input set and N is the sum of elements in the input set.
There are greedy approximation algorithms which can guarantee a difference within 4/3 of the optimum.
but you need it be within 143000000/(285210000-14300
When the number of bits needed to express any number in the set is greater than the size of the set, the probability of finding a perfect partition goes down, so I would suggest approximating the numbers by removing a factor of 143000000*2-285210000 and then applying a pseudo-polynomial time algorithm