My opinion is that this is too big array and it's size is not even
function of count of the sums.
I will try to give you one other algo it's something like O(n!) I'm not
sure about this butt I think it will make the work:
The idea in it is to generate all the posible sums which are a solution
and choose the best.
1. put all the sums in a array ordered descendantly:
givenSums[] = {40144.66, 32490.50 , 35985.55, 28655.78, 20295.13,
10195.69}
2. make one array called a Solution[] which will contain the final
result This array is the same size as givenSums but it will contain
only 1 and 0 . 1 means that the item exists in the solution and 0
means that it does not exist in the solution.
3. make one array called currentlyTakenSums[] which will contain the
currently taken sums. It is something like the Solution but contains
the current state
4. Recursively try to generate all the posible solutions and choose the
best
Let's say the sum which you are trying to make is Sum = 42,674.12
and Tolerance = 1000
class Solution{
static boolean aSolutionExists;
double static givenSums[] = {40144.66, 32490.50 , 35985.55, 28655.78,
20295.13, 10195.69};
int static currentlyTakenSums[] = {0,0,0,0,0,0};
int static Solution[] = {0,0,0,0,0,0};
static double SolutionSum = 0;
static double SolutionTolerance = Double.MAX_VALUE;
static final double Sum = 42,674.12;
static final double Tolerancce = 1000;
static double curentSum = 0;
static double currentTolerance = Double.MAX_VALUE;
static void printSolution(){
for(int i=0;i<Solution.size;i++){
if(Solutions[i] == 1){
System.out.println( givenSums[i] +"," );
}
}
}
static void copyCurrentSolution(){
SolutionTolerance = currentTolerance;
SolutionSum = currentSum;
for(int i=0;i<currentlyTakenSums.size;i++){
Solution[i] = currentlyTakenSums[i];
}
}
static void findASolution(currentIndex){
currentlyTakenSums[currentIndex] = 1;
double sumToAdd = givenSums[currentIndex];
curentSum += sumToAdd;
if(curentSum>Sum && curentSum<=Sum+Tolerance ){
//found a Solution
currentTolerance = curentSum -Sum;
if( currentTolerance < SolutionTolerance){
//found a better solution
copyCurentSolution();
}
}
if(curentSum<Sum && currentIndex<givenSums.size - 1){
findASolution(currentIndex +1);
}
curentSum -= sumToAdd;
currentlyTakenSums[currentIndex] = 0;
}
main(){
findASolution(0);
if(aSolutionExists) printSolution();
else System.out.println("Solution does not exist");
}
}//end class
I didn't try the code but I think it should work with some fixes on
java.
Regards
