2
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ What do you mean by the stackIds? How do you measure the "efficiency" of a combination? Your question is very clear overall, this is just the only thing that I don't understand. \$\endgroup\$ – Simon Forsberg May 1 '15 at 9:23
  • \$\begingroup\$ And how is a packet related to the combinations? \$\endgroup\$ – Simon Forsberg May 1 '15 at 9:25
  • \$\begingroup\$ The idea is that you have 2 bins that are for example 10 big. you have an arraylist full of packets that you need to devide in a left bin, or in a right bin. I want to run this function. put the optimal combination of packets that equals 10 in the left bin. and the rest of the packages in the right bin untill the last package goes in the left bin and rerun the function untill i reach the end of the arraylist \$\endgroup\$ – ewart May 1 '15 at 9:40
  • \$\begingroup\$ thus if i use a combination that equals 10 with a lower stackId i can rerun the function wasting less numbers in the arraylist. so when i go through the whole arraylist i can find a better way to fill both bins \$\endgroup\$ – ewart May 1 '15 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.