算法：基于属性和提取子集

小编典典

算法：基于属性和提取子集

algorithm

我想要一种算法（无特定语言）从一组整数中找到一个子集，以使它们的总和在一定范围内。

例如，如果我有一群人，其权重如下。

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的赏金…但是，如果有一个不错的解决方案，我会在时机成熟时予以发放。

阅读 244

2020-07-28

共1个答案

小编典典

这类似于0-1背包问题或子集和问题。

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

这是动态编程算法的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));

2020-07-28