算法：根据物业之精华集 [英] Algorithm: Extract subset based on property sum

问题描述

欲一个算法（无特定语言）来找到从一个整数集，使得它们的和是在一定范围内的一个子集

I want an algorithm (no specific language) to find a subset from a set of integers such that their sum is within a certain range.

例如，如果我有一群人，都是它们的权重如下：

For example, if I have a group of people, whose weights are as follows.

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

现在，从这些人，我想找到一个子集，其总重量为818-822磅之间（如果你正在尝试做数学题......不要怕麻烦，这些数字是从我的头，我甚至不知道是否有这个数据集的解决方案）。人的组中的号也没有关系，只是一组从较大集合。真的，任何一组会做（尽管随机在我的情况好）。

Now, from these people, I'd like to find a subset whose combined weight is between 818-822 pounds (If you're trying to do the math... don't bother, these numbers are out of my head, and I don't even know if there's a solution with this dataset). The number of people in the group doesn't matter, just a group from the larger set. And really, any group will do (although random is better in my case).

请注意，这只是一个简单的例子...有实际上是数百人，这将是可能的，不会有什么组合，将融入这一标准。由于实际数字会比这个大很多，我很担心的n次方的问题，并通过数千次迭代的运行，即使我想这能非常迅速地运行。

Note that this is just a quick example... there would actually be hundreds of people, and it would be possible that there would be no combination that would fit into this criteria. Because the actual numbers would be much larger than this, I'm concerned about a n^n problem and running through thousands of iterations, even though I need this to run very quickly.

也许我在那一天在计算机科学类睡着了，但我一直没能拿出什么比暴力方法等。

Maybe I fell asleep during that day in computer science class, but I haven't been able to come up with anything other than brute force methods.

我已经标记这是JavaScript的，只是因为这是最接近我的实际执行（和读取更容易）。开到其他的解决方案，只要它们不pdicated某些邪神功能$ P $某处

I've tagged this as javascript, simply because that is closest to my actual implementation (and it reads easier). Open to other solutions, as long as they aren't predicated on some Cthulhu function somewhere.

我知道这是一个奇怪的问题要问的SO，但这里的任何帮助将是AP preciated。

I know this is a weird question to ask on SO, but any help here would be appreciated.

好吧，我难倒。 23至发布赏金的东西，我可以神交code-明智的 - 我的背景是肯定不会在这个领域，我有一个困难时期，甚至挑剔用来说明问题的符号，更别说解决方案。

Ok, I'm stumped. 23 hours to post a bounty for something that I can grok code-wise -- my background is certainly not in this realm, and I have a hard time even discerning the notations used to describe the problem, let alone the solutions.

任何人想帮助我，并把我的一些样本JavaScript的code，我可以修改到最终的项目？我将添加一个250pt赏金的时候，我可以......但是，如果一个体面的解决方案还通过我的手它在时机成熟时。

Anybody want to help me out and throw me some sample javascript code that I can modify to the final project? I'll be adding a 250pt bounty when I can... but if a decent solution comes through I'll hand it out when the time comes.

推荐答案

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

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

If weights are not very large integer numbers, a dynamic programming solution should be efficient.

下面是JavaScript实现的动态规划算法。如果你想随机组，只是随机洗牌的人员列表应用此算法之前。

Here is javascript implementation of dynamic programming algorithm. If you want random groups, just random shuffle the list of people before applying this algorithm.

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));

这篇关于算法：根据物业之精华集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！