javascript - 算法:根据属性总和提取子集

Question

我想要一个算法(没有特定的语言)从一组整数中找到一个子集，使得它们的总和在某个范围内。

比如我有一群人，他们的体重如下。

var people:{
   jane:126,
   julia:112,
   charles:98,
   john:182,
   bob:213,
   edgar: 237,
   jay: 223,
   dan: 191,
   alex: 210,
   david: 196
}

现在，我想从这些人中找到一个子集，其总重量在 818-822 磅之间(如果你想做数学......别费心了，这些数字不在我的范围内头，我什至不知道这个数据集是否有解决方案)。小组中的人数无关紧要，只是从较大的一组中选出一组。实际上，任何组都可以(尽管在我的情况下随机更好)。

请注意，这只是一个简单的示例……实际上会有数百人，并且可能没有符合此条件的组合。因为实际数字会比这大得多，所以我担心 n^n 问题并运行数千次迭代，即使我需要它运行得非常快。

也许那天我在计算机科学课上睡着了，但除了蛮力方法，我什么也想不出来。

我将其标记为 javascript，只是因为它最接近我的实际实现(而且读起来更容易)。对其他解决方案持开放态度，只要它们不以某处的某些 Cthulhu 功能为前提。

我知道在 SO 上提出这个问题很奇怪，但我们将不胜感激。

---

好吧，我被难住了。 23 小时为我可以在代码方面理解的东西发布赏金——我的背景肯定不在这个领域，我什至很难辨别用于描述问题的符号，更不用说解决方案了。

有人愿意帮助我并向我提供一些我可以修改为最终项目的示例 javascript 代码吗？我会在可能的时候增加 250pt 的赏金……但如果有合适的解决方案，我会在适当的时候分发。

Answer 1

这类似于 0-1 Knapsack problem或 Subset sum problem .

如果权重不是很大的整数，动态规划解决方案应该是有效的。

---

这里是动态规划算法的javascript实现。如果您想要随机分组，只需在应用此算法之前随机打乱人员列表即可。

var p = {
   jane:126,
   julia:112,
...
};

function subset(people, min, max)
{
  var subsets = [];
  subsets[0] = '';

  for (var person in people)
  {
    for (var s = min-1; s >= 0; --s)
    {
      if (s in subsets)
      {
        var sum = s + people[person];

        if (!(sum in subsets))
        {
          subsets[sum] = subsets[s] + ' ' + person;

          if (sum >= min && sum <= max)
          {
            return subsets[sum];
          }
        }
      }
    }
  }

  return 'Not found';
}

print(subset(p, 818, 822));