14

合計が特定の範囲内になるように、整数のセットからサブセットを見つけるアルゴリズム (特定の言語ではない) が必要です。

たとえば、重みが次のような人々のグループがあるとします。

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 問題が発生し、何千回も繰り返し実行されることを懸念しています。

その日、コンピューター サイエンスの授業中に居眠りをしたのかもしれませんが、力ずくの方法以外は思いつきませんでした。

これを javascript としてタグ付けしましたが、これは実際の実装に最も近い (そして読みやすい) からです。どこかのクトゥルフ機能に基づいていない限り、他のソリューションを受け入れます。

SOでこれを尋ねるのは奇妙な質問だと思いますが、ここで何か助けていただければ幸いです。

わかりました、私は困惑しています。コードに関して理解できる何かの報奨金を投稿するのに23時間-私のバックグラウンドは確かにこの領域にありません。解決策は言うまでもなく、問題を説明するために使用される表記法を識別することさえ困難です。

誰かが私を助けて、最終的なプロジェクトに変更できるサンプル JavaScript コードを投げてくれませんか? できれば 250pt の報奨金を追加します...しかし、適切な解決策が得られた場合は、その時が来たらそれを配布します.

4

4 に答える 4

10

これは、 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));
于 2012-10-09T20:32:23.020 に答える
4

これは、「バイナリ ナップザック問題」のバリエーションのように見えますが、最適な値がまだ許容範囲外である場合、答えが拒否されるという境界が追加されています。

「多項式時間近似」を調べることができます。

1 つの方法として、セットを重みで並べ替えることが考えられます。ダン、ジョン、デビッド、アレックスを取得すると、779 になります。ジェーンを追加すると、905 に達し、87 では多すぎます。下の名前、ジュリア、112 をチェックして、違いが最も近いものを探します。Alex を Julia (210-112) と交換すると 98 を失うことになり、David を Julia と交換すると 84 を失うことになります。

ソートのアルゴリズムは O(n log n) で、設定サイズに依存します。いくつかの欠点があります (収束が保証されない、グループが隣接しがちになる、出発点の近くに人が集まるなど) が、「グループ」だけが必要な場合は十分かもしれません。

アルゴリズムを再帰的に実装することもできます。最悪の場合は O(n^3 log n) になりますが、実際に人間と一緒に作業している場合 (適度に狭い範囲にクラスター化された重み、滑らかな曲線)、収束はかなり速くなる可能性があります。

于 2012-10-09T20:32:57.553 に答える
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 に進みます。わかりました。1 件の一致が見つかりました。このプロセスを続けることで、すべての一致を見つけることができます。基本的に、ブラケットが行うことは、可能なすべての組み合わせのサブセットのみを検索するのに役立つため、すべての組み合わせをチェックする必要はありません。どちらか一方からではなく、平均から外側に組み合わせを生成しています。

合計が範囲を超える/下回るときはいつでも、ハイサイド/ローサイドで組み合わせ生成を終了し、もう一方に切り替えます。これが問題の最適な解決策です。

実装方法: このアルゴリズムを実装するには、「辞書順」で機能する組み合わせジェネレーターを取得する必要があります。次に、n 個、たとえば 5 個のアイテムから始めて、上で示したように中央値の組み合わせを決定します。次に、次に低い組み合わせを取得します。低い場合は、次に高い組み合わせに切り替えます。

-------------- 追記 -------------------

これについて考えた後、辞書編集コンビネーターではなく、単純な変更タイプのアルゴリズムを使用する方が良いかもしれません。このタイプのアルゴリズムはすべての組み合わせを生成しますが、一度に 2 つの要素のみを切り替えます。基本的に、このアルゴリズムを変更して、範囲外になる (範囲を超えるか下回る) たびに方向を切り替えるようにします。

于 2012-10-09T21:11:05.180 に答える
1

同様の質問に対する答えは次のとおりです配列内の要素の組み合わせの合計で、その合計が指定された数値に等しい

<?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
于 2014-01-15T14:33:51.610 に答える