Find the lowest combination of predefined numbers, which sum is higher than X

Question

lets say I have an array with different item-prices.

var myItemsEuro = [0.34, 0.11, 0.5, 0.33, 0.05, 0.13, 0.23, 3.22, 1.94]

I would like to have function like this:

function getTradeItems(0.89) {   //The price of the item I want to buy

    //Calculate, which of my items should be used to buy the item for 0.89€

    return [0, 3, 6]    //The position of my items in the array, which added together equal 0.90€

}

To clear things up:
I have a box of items with pricetags on them (myItemsEuro). I want to buy an item, using my items as a payment. The other party will accept my trade, if I overpay with atleast one cent. The function should work, so i can pass the other guy's price to it (0.89 for example) and it returns, which items I will have to give away. The combination of these items must be above 0.89 cents (atleast 0.9), but should be as low as possible!

I am quite new to JS, and I was thinking about calculating every single combination of my items and then use the one that has the lowest difference to the buyprice. This seems really complicated to me and I don't even know how I would make it calculate every single combination and also save which items were used for the calculation.

Is there any way to achieve this a bit more efficient? I don't really expect any perfectly working code here, a little bit of help to get into the right direction would also be nice.

Any help is appreciated! :)

---

Edit:

Sorry for missing my own attempt. It's just that I have no idea how I should solve this at all. And no - not homework - this is supposed to be part of a chromeextension I am working on!

var myItemsEuro = [0.34, 0.11, 0.5, 0.33, 0.05, 0.13, 0.23, 3.22, 1.94]

function getTradeItems(marketPrice) {

 var result = 0;

 var positions = [];

 for(i = 0; i < myItemsEuro.length; i++) {

  result += myItemsEuro[i]; //add numbers from the array

  positions.push(i); //save the used numbers position

  if(result > marketPrice) { //if result is greater than marketPrice...

   console.log(result)
            console.log(positions)

   return positions; //return positions in the array

  }
 
 }
}

getTradeItems(1.31);

---

Edit:

Sorting the array and then adding up numbers doesn't give a solution.

var x = 1.18;

   //Sorted by numbers
var myItemsEuro = [0.05, 0.11, 0.13, 0.20, 0.35, 0.50, 0.60, 0.69, 0.75];

   //Add together and stop when sum > x:
0.05 + 0.11 + 0.13 + 0.20 + 0.35 + 0.50 = 1.34

   //Best solution would be adding [6] and [8] from the array
0.50 + 0.69 = 1.19  

Answer 1

You could use a brute force approach and test all combinations of the items if they are greater or equal of the target.

The base consideration is to take a counter from zero up to 2^{values.length} and check if the actual 2^index is part of the counter with a bitwise AND &. If so, take the value from the index and put it into the parts array.

Then build the sum of the parts and check if sum is greater or equal of target and possibly smaller than sum in result array, then move the result to the result array. If sum is equal to result[0].sum, then push the actual parts and sum to the result.

This proposal works with unsorted values, but could be more efficient, if the values which are greater then the target value are not included in the array to work on.

Another draw back is the fact, that bitwise arithmetic works only with 32 bit, that means arrays with more items than 32 are not possible use.

var values = [0.34, 0.11, 0.5, 0.33, 0.05, 0.13, 0.23, 3.22, 1.94],
    target = 0.90,
    i,
    l = 1 << values.length,
    result = [],
    parts,
    sum;

for (i = 0; i < l; i++) {
    parts = values.filter(function (_, j) {
        return i & 1 << j;
    });
    sum = parts.reduce(function (a, b) { return a + b; }, 0);
    if (sum >= target) {
        if (!result.length || sum < result[0].sum) {
            result = [{ parts: parts, sum: sum }];
            continue;
        }
        if (sum === result[0].sum) {
            result.push({ parts: parts, sum: sum });
        }
    }
}

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

I would suggest some measures to take:

• Fractional numbers can cause floating point precision issues, so it is better to first convert every value to an integer (i.e. value in cents)
• Perform a recursive search, where at each recursion level you'll decide whether or not to take the item at the corresponding index.
• Think of situations where you might have multiple solutions: maybe in those cases you want to give precedence to solutions that use fewer items. So you would need to keep track of the number of items selected.

The solution I propose here will backtrack as soon as it is clear there is no sense in continuing adding items. There are at least two situations where you can draw this conclusion (of stopping the recursive search):

• When the sum of the values selected so far is already greater than the target value, then there is no sense in adding more items (via recursion)
• If after adding an item at position i, it becomes clear that adding all of the remaining items (via recursion) leads to a sum that is lower than the target, then it makes no sense to not select the item at position i, and repeat the recursive search, as that certainly will not reach the target value either.

Here is the suggested code:

function getTradeItems(target, items) {
    var best = -1e20, // should be maximised up to -1 if possible
        bestTaken = [], // indices of the best selection
        bestCount = 0, // number of selected items in best solution
        // Multiply all amounts by 100 to avoid floating point inaccuracies:
        cents = items.map( euro => Math.round(euro * 100) );
    function recurse(target, i, count) {
        if (target < 0) { // Found potential solution
            // Backtrack if this is not better than the best solution
            // found so far. If a tie, then minimise the number of selected items
            if (target < best || 
                target === best && count > bestCount) return false;
            best = target;
            bestTaken = [];
            bestCount = count;
            return true;
        }
        // Give up when there's not enough item value available
        if (i >= cents.length) return null;
        // Include the item at index i:
        var res1 = recurse(target - cents[i], i+1, count+1);
        // If we could not reach the target, don't lose time retrying
        // without this item:
        if (res1 === null) return null;
        // Exclude the item at index i:
        var res0 = recurse(target, i+1, count);
        // If neither led to a solution...
        if (!res0 && !res1) return false;
        // If the best was to include the item, remember that item
        if (!res0) bestTaken.push(i);
        return true;
    }
    recurse(Math.round(target * 100), 0);
    return bestTaken.reverse();
}

// Sample input
var myItemsEuro = [0.05, 0.11, 0.13, 0.20, 0.35, 0.50, 0.60, 0.69, 0.75];
var x = 1.18
// Get the best item selection
var result = getTradeItems(x, myItemsEuro);
// Output result
console.log('Selected: ', result.join()); // 5, 7
// Show corresponding sum: (1.19)
console.log('Sum: ', result.reduce( (sum, i) => sum + myItemsEuro[i], 0).toFixed(2));