时间戳

首页 > 解决方案 > 有效地推导出数组的哪些元素已被求和

javascript - 有效地推导出数组的哪些元素已被求和

问题描述

我有一个输入数组，如下所示：

const dels = [ // up to 50 possible
  {no: 491, weight: 1348},
  {no: 492, weight: 694},
  {no: 1054, weight: 4104},
  {no: 1181, weight: 2636},  // *
  {no: 2096, weight: 4084},
  {no: 2201, weight: 4064},
  {no: 2296, weight: 2364},
  {no: 2365, weight: 1670},
  {no: 2632, weight: 4084},
  {no: 2891, weight: 2424},
  {no: 3051, weight: 2414},  // *
];

我也有一个总和数组，如下所示：

const sums = [5050, 24836]; // up to 4 possible

结构是固定的，但数量未知（来自外部来源）。

我知道数组的每个数字都是另一个数组的某些成员sums的总和（每个项目只计算一次）。weightdels

所以可以假设：

const sumDels = dels.reduce((a,i) => a + i.weight, 0);
const sumSums = sums.reduce((a,i) => a + i, 0);
sumDels === sumSums // is true

sumDels.every(x => x.weight > 0) // is true

什么算法可以有效地给我导致给定总和的可能组合？

可能的结果如下所示：

const goodResult = [ // <-- array of possible combinations (theretically, there could be more than one)
  [                  // <-- `dels` array mapped with `sumIdx`
    {no: 491, sumIdx: 1},
    {no: 492, sumIdx: 1},
    {no: 1054, sumIdx: 1},
    {no: 1181, sumIdx: 0},  // *
    {no: 2096, sumIdx: 1},
    {no: 2201, sumIdx: 1},
    {no: 2296, sumIdx: 1},
    {no: 2365, sumIdx: 1},
    {no: 2632, sumIdx: 1},
    {no: 2891, sumIdx: 1},
    {no: 3051, sumIdx: 0},  // *
  ]
];

一个天真的解决方案会尝试所有排列，但 sums.length==4 和 dels.length==50 是 1267650600228229401496703205376 可能的组合，如果我没记错的话...... ;-)

标签： javascriptarraysalgorithm

解决方案

正如评论中所建议的，这被称为子集和问题，我了解到通常没有其他方法可以尝试所有组合，同时在组合已经被确定为错误时尽早退出。

这让我得到了另一个 Stackoverflow 答案，它有一个很好的递归实现。

虽然它只处理一个总和（我的sums数组最多可以达到 4 个数字），但它是完整解决方案的一个很好的起点。

推荐阅读