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

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函数的。

我知道这是一个奇怪的问题，但任何帮助都将不胜感激。

---

好吧，我被卡住了。我要花23个小时发布一份赏金，寻求一个我可以理解代码的东西--我的背景当然不是在这个领域，我甚至很难辨别用于描述问题的符号，更不用说解决方案了。

有人可以帮我并提供一些示例JavaScript代码，我可以将其修改为最终项目吗？ 当我能够添加250pt赏金时，我会发布的......但如果有一个像样的解决方案出现，我会在适当的时候发布赏金。

- John Green

---

这让我想起了一个一维装箱问题。你考虑过类似这样的东西吗？ - im so confused

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

- Evgeny Kluev

---

如果我们遍历不同大小的集合（从查找1个元素集开始），然后在每个阶段从所需总和中减去平均重量（例如，在3个元素时，减去812/3）所有值，我们就得到了子集求和问题（总和应为零）。 - Phil H

+1 是为了帮助我更好地理解问题的本质。现在我只需要想办法如何编写它。 - John Green

坦白说，我自己想不出来这个（特别是因为我的数据是双精度浮点数，而且我没有从哈希开始）。它看起来很简单，但它的优雅中隐藏着复杂性。+250。 - John Green

Answer 2

看起来像是 "二进制背包问题" 的变种，加上了一个范围限制，如果最佳匹配仍然超出可接受范围，则会被拒绝。

您可能需要了解 "多项式时间近似"。

一种方法是按重量对集合进行排序。然后你从中间向下和向上查找：你得到丹尼斯、约翰、大卫、亚历克斯，你在 779。你添加简，发现自己在 905，比预期的多了 87；所以你检查下面的名字，朱莉娅，那是 112，在差异之间寻找最接近的匹配。用朱莉娅交换亚历克斯（210-112）会让你损失 98，用朱莉娅交换大卫会损失 84。反复进行此操作。

算法的时间复杂度为 O(n log n) 用于排序，然后取决于集合大小。它有几个缺点（不能保证收敛，组将倾向于连续，它将聚集在起始点附近等），但如果您只想要 "一个组"，这可能已经足够了。

您也可以递归地实现算法。最坏的情况是 O(n^3 log n)，但如果您真的在处理人类（权重聚集在相当小的范围内，平滑曲线），收敛很可能会非常快。

- LSerni

---

+1 是为了帮助我更好地理解问题的本质。现在我只需要想办法如何编写它。 - John Green

Answer 3

这就是所谓的“排序和括号”问题。解决它的方法是对数据进行排序，然后在目标值或目标范围周围加上括号。

例如，在这种情况下，排序顺序如下：

98 112 126 182 191 196 210 213 223 237

现在你可以求出列表的平均值：178.8。因此，起始括号是（126,182）。从平均值开始向外移动：sum(126,182,112,191,98) = 709，太小了。删除98并用另一边的值替换：196，即sum(126,182,112,191,196) = 807，仍然太小。转到高侧的下一个值，sum(126,182,112,191,210)=821。好的，找到一个匹配。通过继续这个过程，你可以找到每一个匹配。基本上，括号化帮助你只搜索所有可能组合的子集，因此你不必检查每个组合。你是从平均值向外生成组合，而不是从一端或另一端生成。

每当你的总和超过/低于范围时，你就会在高/低侧终止组合生成，并切换到另一侧。这是问题的最优解。

实现方法：要实现这个算法，你需要获得一个按字典顺序工作的组合生成器。然后你从n（比如5）个项目开始，并确定中位数组合，就像我上面展示的那样。然后你获得下一个较低的组合，如果你太低了，你就切换到下一个更高的组合，依此类推。

-------------- 附录 -------------------

经过思考，使用简单的变化算法可能比使用字典序组合器更好。这种类型的算法将生成所有组合，但每次只交换任意2个元素。基本上，你修改这个算法以在超出范围时（超出范围或低于它）改变方向。

- Tyler Durden

---

这绝对是一种不同（更适合程序员的）解决问题的方式。在阅读了“标准”子集和问题的实现后，你的解决方案一开始让我感到不足，但是我越想它需要如何工作，我就越喜欢它。它具有很大的速度潜力，因为它将非常好地权衡曲线中间部分与我的数据集的特定性（尤其是如果我能够从一开始就正确猜测项目数量）。最大的缺点是实现所需的代码可能会对除实现者以外的任何人来说都很难理解。:) - John Green

这不是问题的最佳解决方案。它对于可能输入的特定子集效果很好，但对于其他输入性能较差。 - argentage

Answer 4

这里是类似问题的答案 在数组中找到元素组合的和等于给定数字

<?php

$limit = 12;
$array = array(6,1,10,4,1,3,11,2,15,5,12,10,17);

echo implode(', ',$array).'<br>';

// remove items 15 and 17 because they are great then $limit = 12
$array = array_filter($array, function($var) use ($limit) {
  return ($var <= $limit);
});

rsort($array);
echo implode(', ',$array);

// the algorithm is usable if the number of elements is less than 20 (because set_time_limit)
$num = count($array); 

//The total number of possible combinations 
$total = pow(2, $num);

$out = array();

// algorithm from http://r.je/php-find-every-combination.html
// loop through each possible combination  
for ($i = 0; $i < $total; $i++) {  

    $comb = array();

    // for each combination check if each bit is set 
    for ($j = 0; $j < $num; $j++) { 
       // is bit $j set in $i? 
        if (pow(2, $j) & $i){
          $comb[] = $array[$j];
        }      
    } 

    if (array_sum($comb) == $limit)
    {
      $out[] = $comb;
    }
}

array_multisort(array_map('count', $out), SORT_ASC, $out);

$out = array_unique($out, SORT_REGULAR);

foreach($out as $result) echo implode(', ', $result).'<br>';

这段代码的输出是和为 $limit(12)... 的组合列表。

12
10, 2
11, 1
5, 4, 3
6, 4, 2
6, 5, 1
10, 1, 1
5, 4, 2, 1
6, 3, 2, 1
6, 4, 1, 1
5, 3, 2, 1, 1

- revoke