一尘不染

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

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


阅读 198

收藏
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