寻找数字的最佳可能子集组合以达到给定的总和或最接近给定的总和

Question

所以，我有这个问题需要解决，显然这叫做 子集求和问题，除了我需要得到子集，而不仅仅是当它与给定数字完全一致时，但最接近的情况是没有达到给定数字的确切总和，它不应该超过参考数字，只在下面，如果有两个以上的可能子集具有相同的结果，我想得到分布较好的子集，数组中从大数到小数优先，并限制每个子集不超过10次相同的数，允许重复，例如：

这是具有预定义值的数组：

let num = [64.20, 107, 535, 1070];

和给定的数字：

let investment = 806.45

一个可能的解决方案是：

[0, 2, 1, 0] // this sums up to 749 (since there is no way to get to 806.45 with the given array)

请注意这个结果是指允许nums中的每个值达到总和的次数：

但更好的解决方案是：

[4, 5, 0, 0] // this sums up to 791.80 (since there is no way to get to 806.45 with the given array)

还有一个更好的解决方案（因为首先考虑了较高的值而不是较低的值）

[4, 0, 1, 0] // this sums up to 791.80 also but you can see it's taking a higher value when possible.

另一个重要的限制是永远不要给出负面结果。

到目前为止我已经这样尝试过（在 VueJS 中）：

getPackages(){
      let investment = 806.45;
      const num = [64.20, 107, 535, 1070]
      let a, b, c, d;
      let results = [];

      a = investment / num[0] >= 0 ? (investment/num[0]) : 0;
      b = investment / num[1] >= 0 ? (investment/num[1]) : 0;
      c = investment / num[2] >= 0 ? (investment/num[2]) : 0;
      d = investment / num[3] >= 0 ? (investment/num[3]) : 0;

      let dResult = [], cResult = [], bResult = [], aResult = [];

      for (let i = 0; i <= d; i++){
        if (i>0){
          dResult.push((i * num[3]))
        }
      }

      for (let i = 0; i <= c; i++){
        if (i>0){
          cResult.push((i * num[2]))
        }
      }

      for (let i = 0; i <= b; i++){
        if (i>0){
          bResult.push((i * num[1]))
        }
      }

      for (let i = 0; i <= a; i++){
        if (i>0){
          aResult.push((i * num[0]))
        }
      }

      let aResultCoincidences = [];
      let bResultCoincidences = [];
      let cResultCoincidences = [];
      let dResultCoincidences = [];

      bResult.forEach(value => {
        aResult.findIndex(item => item === value) > 0 ? bResultCoincidences.push(aResult.findIndex(item => item === value)) : null
      })

      aResult.splice(0, Math.max(...bResultCoincidences) + 1)

      cResult.forEach(value => {
        bResult.findIndex(item => item === value) > 0 ? cResultCoincidences.push(bResult.findIndex(item => item === value)) : null
      })

      bResult.splice(0, Math.max(...cResultCoincidences) + 1)

      dResult.forEach(value => {
        cResult.findIndex(item => item === value) > 0 ? dResultCoincidences.push(cResult.findIndex(item => item === value)) : null
      })

      cResult.splice(0, Math.max(...dResultCoincidences) + 1)

      this.package1 = aResult.length
      this.package2 = bResult.length
      this.package3 = cResult.length
      this.package4 = dResult.length

    },

我的方法是尝试从每次乘法中获得所有可能的结果，然后删除与我用这种组合制作的数组之间匹配的结果，最终得到结果，但这不是优化得很好，我相信这个问题可能有更好的解决方案。

无论如何忽略 vuejs 实现，那只是在 DOM.

中设置值

***ES6 解决方案会很棒。

要玩的 CodeSandbox：CODESANDBOX LINK

提前致谢。

Answer 1

让我们首先考虑 2 变量的情况。我们想找到两个数字 x1, x2 使得

f(x1,x2) = 64.20 * x1 + 107 * x2 - 806.45

如果我们让x1,x2 为实数，那么这只是一条直线方程。在这个问题中，我们只需要正整数解，即网格点。我用红色线上方的网格点和蓝色线下方的网格点绘制得很糟糕。然后问题是找到最接近该线的网格点。

请注意，有很多点我们永远不需要考虑，只有红色和蓝色网格点是可能的候选点。

生成彩色网格点非常简单。我们可以循环遍历从0到13的x1值，通过求解方程

计算出真正的x2值

x2 =  (806.45 - 64.20 * x1)/107

并找到地板（x2）和天花板（x2）。稍微好一点的是循环 x2，其中运行从 0 到 8 求解 x1

x1 =  (806.45 - 107 * x2)/64.20.

另一种方法可能是某种零跟踪例程。如果你在给定的网格点 (x1,x2) 计算 f(x1,x2) 如果它小于 0 我们需要考虑 (x1+1,x2) 或 (x1,x2+1)，如果 f(x1 ,x2) 大于零考虑 (x1-1,x2) 或 (x1,x2-x1)。我不认为这种方法的复杂性真的带来任何好处。

如果我们现在转向 3D，我们将得到一个包含三个变量 x1、x2、x3 的方程

f(x1,x2,x3) = 64.20 * x1 + 107 * x2 + 535 * x3 - 806.45

这定义了一个 3D 平面，要求所有变量都是非负的，将其限制在平面的三角形部分。

要在这里找到候选点，我们可以遍历可能的整数对 (x1,x2)，然后找到确切的 x3 值

x3 = (806.45 - 64.20 * x1 - 107 * x2)/ 535

及其地板和天花板。候选 (x1,x2) 仅在候选三角形中连线，因此我们可以使用以下过程。

// First find max possible x1

x1_max = ceil(806.45/64.20)
for(x1 = 0; x1< x1_max; ++x1) {
   // for a given x1 find the maximum x2
   x2_max = ceil((806.45 - 64.20*x1)/107)
   for(x2=0;x2<x2_max;++x2) {
       // for a given (x1,x2) find the exact x3
       x3 = (806.45 - 64.20 * x1 - 107 * x2)/ 535
       // and its floor and ceiling
       x3l = floor(x3); x3h = ceil(x3);
       add_to_candidates(x1,x2,x3l);
       add_to_candidates(x1,x2,x3h);
   }
}

一旦你可以简单地 select 绝对值最小的候选人。

类似的想法可以扩展到更多变量。

Answer 2

这是一种方法。我没有仔细看你的，也不知道这是否比它有任何优势。

这是一种蛮力方法，只需对每个类别的潜在单个值进行叉积，将总和相加，然后缩小列表以找到最接近目标的所有选项。我最初写的略有不同，试图捕捉最接近目标的值。

这是一个带有几个辅助函数的实现：

const sum = (ns) =>
  ns .reduce ((a, b) => a + b, 0)

const crossproduct = (xss) => 
  xss.reduce((xs, ys) => xs.flatMap(x => ys.map(y => [...x, y])), [[]])

const range = (lo, hi) =>
  [...Array(hi - lo)] .map ((_, i) => lo + i)

const call = (fn, ...args) => 
  fn (...args)

const closestSums = (t, ns) => 
  call (
    (opts = crossproduct (ns .map (n => range (0, 1 + Math .ceil (t / n))))) => 
      opts .map (xs => [xs, sum (xs .map ((x, i) => x * ns [i]))])
      .reduce (
        ({best, opts}, [opt, tot]) => 
          call (
            (diff = t - tot) => 
              diff >= 0 && diff < best
                ? {best: diff, opts: [opt]}
              : diff >= 0 && diff == best
                ? {best, opts: [...opts, opt]}
              : {best, opts}
          ),
          {best: Infinity, opts: []}
        ) .opts
  )

const byHigher = (as, bs) =>
  as .reduceRight ((r, _, i) => r || (as[i] < bs[i] ? 1 : as[i] > bs[i] ? -1 : 0), 0)

const closestCounts = (t, ns) => 
  closestSums (t * 100, ns .map (n => 100 * n)) 
    .filter (cs => cs.every(c => c <= 10))
    .sort (byHigher)

console .log (
  closestCounts (806.45, [64.20, 107, 535, 1070]),
  closestCounts (791.8, [64.20, 107, 535, 1070])  // exact match
)

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

请注意，包装器将所有内容乘以 100 以消除小数点和潜在的浮点舍入错误。如果不行，添加一些匹配容差就足够了。

最后的排序是幼稚的，假设您的值是按数字升序排列的。否则，分拣机必须变得更复杂。

正如我所说，这不太可能有效，并且它可能不会对您的版本有任何好处，但它至少是一种不同的方法。

寻找数字的最佳可能子集组合以达到给定的总和或最接近给定的总和

Finding the best possible subset combinations of numbers to reach a given sum or closest to it

javascript

algorithm

math

dynamic-programming

subset-sum