Given list of integers, find the sets of numbers whose sum >= a target number, minimising the total amount that each set goes over the target

Question

So somehow a relative of mine got these restaurant vouchers that can be used to deduct 500 baht off of each receipt. It is possible to ask the restaurant to issue multiple receipts so that multiple vouchers can be used. The relative wishes to spend as little cash as possible (anything over the voucher value of 500 will have to be paid in cash)

More formally, the question is:

given a list of prices (being the prices of items to be ordered), what are the combinations of prices that would require the least amount of cash to be paid?

For example:

let prices = [425, 105, 185, 185, 185, 98, 145, 155, 125, 125, 135, 295, 295, 155, 125]

if I were to just sum the prices in the given order, stopping when sum is over 500:

[425 + 105], [185 + 185 + 185], [98 + 145 + 155 + 125], [125 + 135 + 295], [295 + 155 + 125]

Sums of each combination:

[530, 555, 523, 555, 575]

Amount over 500: [30, 55, 23, 55, 75]

Total cash to pay: 238

What is the best combinations of prices that would require the least amount of cash?

So far I have attempted a brute-force approach by generating all permutations of the prices and calculating the required cash amount for each permutation in the same fashion as the above example (summing from left to right, stopping when >= 500). However, this approach resulted in heap out of memory error when there are more than 10 prices :(

Thanks in advance.

Answer 1

I got 238 as well, with backtracking.

The program below tries all available new combinations of the state:

(index, sum_a, count_a, sum_b, count_b...)

  where index is the index in prices, and sum_x and count_x
  are the distinct sum x and the count of how many bins
  with that sum we currently have.

It returns the recorded value achieved from that state if the state was previously seen, and avoids searching a branch known to lead to a result greater than or equal to the smallest recorded result so far. It recurses using a single object to store the state in memory and updates it as it backtracks.

There's also a tweak-able bound on how large a bin is allowed be (the line, if (new_sum >= 1.2 * 500)).

function getPrefixSums(A){
  let pfxs = new Array(A.length);
  pfxs[-1] = 0;
  A.map((x, i) => pfxs[i] = A[i] + pfxs[i-1]);
  return pfxs;
}

function add(sum, new_sum, dp){
  if (dp.state[sum] == 1)
    delete dp.state[sum];
  else if (dp.state.hasOwnProperty(sum))
    dp.state[sum] -= 1;
  if (dp.state.hasOwnProperty(new_sum))
    dp.state[new_sum] += 1;
  else
    dp.state[new_sum] = 1;
  if (new_sum > 500)
    dp.total += new_sum - 500;
  else if (new_sum < 500);
    dp.remaining -= new_sum - sum;
}

function remove(sum, new_sum, dp){
  if (sum > 0 && !dp.state.hasOwnProperty(sum))
    dp.state[sum] = 1;
  else if (sum > 0)
    dp.state[sum] += 1;
  if (dp.state[new_sum] == 1)
    delete dp.state[new_sum];
  else if (dp.state.hasOwnProperty(new_sum))
    dp.state[new_sum] -= 1;
  if (new_sum > 500)
    dp.total -= new_sum - 500;
  else if (new_sum < 500);
    dp.remaining += new_sum - sum;
}

function g(prices, pfxs, i, dp, memo){
  const sorted = Object.entries(dp.state).sort(([sum1, count1], [sum2, count2]) =>
    Number(sum1) - Number(sum2));
  const key = String([i, sorted]);
  
  if (memo.hasOwnProperty(key))
    return memo[key];

  if (dp.total >= dp.best)
    return memo[key] = Infinity;
    
  if (i == prices.length){
    if (Object.keys(dp.state).some(x => Number(x) < 500))
      return memo[key] = Infinity;
    dp.best = Math.min(dp.best, dp.total);
    return memo[key] = dp.total;
  }
    
  let best = Infinity;
  let bestSum = -1;
    
  // Add bin
  if (pfxs[pfxs.length-1] - pfxs[i-1] >= 500 + dp.remaining){
    dp.remaining += 500;
    add(0, prices[i], dp);
    
    const candidate = g(prices, pfxs, i+1, dp, memo);
      
    best = candidate;
    bestSum = 0;
    
    dp.remaining -= 500;
    remove(0, prices[i], dp);
  }

  // Add to existing bin;
  for (let sum in dp.state){
    const new_sum = Number(sum) + prices[i];
    
    if (new_sum >= 1.2 * 500)
      continue;
      
    add(sum, new_sum, dp);
      
    const candidate = g(prices, pfxs, i+1, dp, memo);

    if (candidate < best){
      best = candidate;
      bestSum = sum;
    }
      
    remove(sum, new_sum, dp);
  }
  
  return memo[key] = best;
}

function backtrack(prices, total, memo){
  let m = [];
  
  for (let i in memo)
    if (memo[i] == total)
      m.push(i);
 
  m = m.map(x => x.split(',').map(Number));
  m.sort((a, b) => a[0] - b[0]);
  
  function validate(added, removed){
    return added.length == 1 &&
      removed.length < 2 &&
      !added.some(([sum, count]) => count > 1) &&
      !removed.some(([sum, count]) => count > 1);
  }

  function back(i, prev_idx, dp){
    if (i == m.length)
      return dp;

    const [idx, ...cts] = m[i];
    const _dp = cts.reduce(function(acc, x, i){
      if (!(i & 1))
        acc[x] = cts[i+1];
      return acc;
    }, {});

    if (idx == prev_idx)
      return back(i + 1, prev_idx, dp);

    let added = [];
    let removed = [];

    for (let sum in _dp){
      if (!dp.hasOwnProperty(sum))
        added.push([sum, _dp[sum]]);
      else if (dp[sum] > _dp[sum])
        removed.push([sum, dp[sum].count - _dp[sum]]);
    }
    for (let sum in dp){
      if (!_dp.hasOwnProperty(sum))
        removed.push([sum, dp[sum]]);
    }

    if (!validate(added, removed))
      return back(i + 1, prev_idx, dp);

    const [[new_sum, _]] = added;
    let old_bin = [];

    if (removed.length){
      const [[old_sum, _]] = removed;
      const len = dp[old_sum].bins.length;
      old_bin = dp[old_sum].bins[len - 1];

      if (dp[old_sum].count == 1){
        delete dp[old_sum];

      } else {
        dp[old_sum].count -= 1;
        dp[old_sum].bins.length = len - 1;
      }
    }

    if (dp[new_sum]){
      dp[new_sum].count += 1;
      dp[new_sum].bins.push(old_bin.concat(prices[idx-1]));
    } else {
      dp[new_sum] = {
        count: 1,
        bins: [old_bin.concat(prices[idx-1])]
      }
    }

    return back(i + 1, idx, dp);
  }

  function get_dp(row){
    const [idx, ...cts] = row;
    return cts.reduce(function(acc, x, i){
      if (!(i & 1)){
        acc[x] = {
          count: cts[i+1],
          bins: new Array(cts[i+1]).fill(null).map(_ => [x])
        };
      }
      return acc;
    }, {});
  }
  
  const dp = get_dp(m[1]);
  
  return back(2, 1, dp);
}

function f(prices){
  const pfxs = getPrefixSums(prices);
  const dp = {
    state: {'0': 1},
    total: 0,
    remaining: 0,
    best: Infinity
  };
  const memo = {};
  const result = g(prices, pfxs, 0, dp, memo);

  const _dp = backtrack(prices, result, memo);
  const bins = Object.values(_dp).flatMap(x => x.bins);

  return [result, bins];
}

var prices = [425, 105, 185, 185, 185, 98, 145, 155, 125, 125, 135, 295, 295, 155, 125];

console.log(JSON.stringify(prices));
console.log(JSON.stringify(f(prices)));