I want to implement the following function:
Given a target sum, return the combination that equals the target sum and is the most efficiënt combination in the array of an
ArrayList
.
For example:
An ArrayList
with the values 9,3,4,6,4,2,1
Then it will return the best possible combination.
You can add 9 + 1, which returns stackId
6.
You can also add 4 + 6 which returns stackId
3, making this one more efficient.
BestCombo
Class
import java.util.ArrayList;
import java.util.Stack;
public class BestCombo {
/** Set a value for target sum */
private final int target;
private int sumInStack, bestStackId;
private Stack<Packet> stack;
private ArrayList<Packet> bestCombination;
public BestCombo(int arrayLength, int targetNumber) {
this.stack = new Stack<>();
this.bestCombination = new ArrayList<>();
this.target = targetNumber;
this.sumInStack = 0;
// bestStackId is equal to length of data array.
// if arrayLength is higher then 2 times the target bestStackId equals target times 2 to prevent unnecessary calculations.
if( arrayLength > targetNumber * 2) {
this.bestStackId = targetNumber * 2;
} else {
this.bestStackId = arrayLength;
}
}
public int getBestStackId() {
return bestStackId;
}
public ArrayList<Packet> calculateTarget(ArrayList<Packet> data, int fromIndex, int endIndex) {
//if solution uses a lower index then the previous
if (sumInStack == target && fromIndex < bestStackId) {
this.bestStackId = fromIndex;
this.bestCombination.clear();
for (Packet p : stack) {
bestCombination.add(p);
}
}
for (int currentIndex = fromIndex; currentIndex < endIndex && currentIndex < bestStackId; currentIndex++) {
if (sumInStack + data.get(currentIndex).getPacketHeight() <= target) {
stack.push(data.get(currentIndex));
sumInStack += data.get(currentIndex).getPacketHeight();
/*
* Make the currentIndex +1, and then use recursion to proceed
* further.
*/
calculateTarget(data, currentIndex + 1, endIndex);
sumInStack -= stack.pop().getPacketHeight();
}
}
return bestCombination;
}
}
Packet
Class
import java.awt.*;
import java.util.ArrayList;
import java.util.Random;
public class Packet{
private int packetCapacityHeight;
private Color color;
public Packet(int packetCapacityHeight){
/**
* a packet contains a capacity parameter and a color which is randomly generated.
*/
this.packetCapacityHeight = packetCapacityHeight;
Random rand = new Random();
int rc = rand.nextInt(255);
int gc = rand.nextInt(255);
int bc = rand.nextInt(255);
this.color = new Color(rc, gc, bc);
}
public Color getColor() {
return color;
}
public int getPacketHeight() {
return packetCapacityHeight;
}
}
You would call the function with:
BestCombo bo = new BestCombo(Order.size(), 10);
bestCombination = bo.calculateTarget(Order, 0, Order.size());
The size of the ArrayList can be anything. The size of the numbers are randomly chosen.
How can I optimize this function to calculate the best option as fast as possible, avoiding unnecessary calculations?