algorithm - 给定整数列表，找到总和 >= 目标数的数字集，最小化每个集合超过目标的总数量

Question

所以不知何故，我的一个亲戚得到了这些餐厅代金券，可以用来从每张收据中扣除 500 泰铢。可以要求餐厅开出多张收据，以便可以使用多张代金券。亲戚希望尽可能少花钱（超过500的礼券价值必须以现金支付）

更正式地说，问题是：

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?

例如：

让价格=[425, 105, 185, 185, 185, 98, 145, 155, 125, 125, 135, 295, 295, 155, 125]

如果我只是按给定顺序对价格求和，当总和超过 500 时停止：

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

每个组合的总和：

[530, 555, 523, 555, 575]

超过500的金额： [30, 55, 23, 55, 75]

支付现金总额：238

需要最少现金的最佳价格组合是什么？

到目前为止，我已经尝试了一种蛮力方法，通过生成价格的所有排列并以与上述示例相同的方式计算每个排列所需的现金金额（从左到右求和，当 >= 500 时停止）。但是，当价格超过 10 个时，这种方法会导致 heap out of memory 错误:(

提前致谢。

标签： algorithmpartition-problem

Answer 1

我也得到了 238，带有回溯。

下面的程序尝试所有可用的新状态组合：

(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.

如果之前看到过该状态，它会返回从该状态获得的记录值，并避免搜索已知会导致大于或等于迄今为止最小记录结果的结果的分支。它使用单个对象递归将状态存储在内存中，并在回溯时对其进行更新。

对于允许的垃圾箱大小（行，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)));