The algorithm finds a number pair that is as close to budget as possible, and if there are more pairs with same value, the pair with the least difference shall be given out. My algorithm works correctly, but is far too slow. Do you have ideas to improve it?
limit = highest value within budget atm,
i = smaller number of pair,
j = bigger number of pair
long limit = 0;
long i = 0, j = 0;
Arrays.sort(preis);
for (int a = 0; a < preis.length; a++) {
for (int b = a + 1; b < preis.length; b++) {
if (preis[a] + preis[b] > limit && preis[a] + preis[b] <= budget) {
limit = preis[a] + preis[b];
i = preis[a];
j = preis[b];
} else if (preis[a] + preis[b] == limit) {
if (preis[a] > i) {
i = preis[a];
j = preis[b];
}
}
}
}
I'm using Java 8.