user2520051 user2520051 - 4 months ago 17
Java Question

finding the subset with the nearest value to the target if the algorithm find no subset that has the exact sum using stack

private static Stack<Integer> temp = new Stack<Integer>();

public void populateSubset(int[] DATA, int fromIndex, int endIndex, int target) {

if (sumInStack == target) {
check = true ;
Counter ++ ;
print(stack, target);
}


for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

if (sumInStack + DATA[currentIndex] <= target) {
stack.push(DATA[currentIndex]);
sumInStack += DATA[currentIndex];
if (sumInStack >= MaxSumInStack){
temp = stack;
MaxSumInStack = sumInStack;

}

populateSubset(DATA, currentIndex + 1, endIndex, target);
sumInStack -= (Integer) stack.pop();

}
}
}


In subsetSum Algorithm in java, i want to find the subset with the nearest value to the target if the algorithm find no subset that has the exact sum.
In each time i update the sumInsStack, i store the stack and the sum to find the max sum. But finally the temp stack is null and nothing in it, although in each step it gets value. what should i do?
P.S: I also want to print all stacks with the max value.

Answer

If by

temp = stack;

you intend to make a copy of the Stack, that's not what you are doing. You only make the temp variable refer to the same Stack as the stack variable, so it you later empty stack, you also empty temp.

In order to make a copy, you'll have to copy the elements of the original stack to the temp stack explicitly :

temp = new Stack<Integer>();
temp.addAll(stack);