4

重複の可能性:
アルゴリズム: プロパティの合計に基づいてサブセットを抽出する

単純なケースでは、配列があります。

{6, 1, 3, 11, 2, 5,12}

そして、その配列に含まれる要素の合計が12になるすべての組み合わせを知りたいとします。

この場合、次の 4 つの組み合わせが得られます。

  • 12
  • 1 + 11
  • 6 + 5 + 1
  • 1 + 3 + 2 + 6

では、BASIC または PHP でこれを行うにはどうすればよいでしょうか。おそらく疑似コードが最初です;-)。

調べてみたら決まった数の要素の組み合わせしかなかった。

4

4 に答える 4

6

あなたが試すことができます

echo "<pre>";

$sum = 12 ; //SUM
$array = array(6,1,3,11,2,5,12);
$list = array();

# Extract All Unique Conbinations
extractList($array, $list);

#Filter By SUM = $sum
$list = array_filter($list,function($var) use ($sum) { return(array_sum($var) == $sum);});

#Return Output
var_dump($list);

出力

array
  0 => 
    array
      1 => string '1' (length=1)
      2 => string '2' (length=1)
      3 => string '3' (length=1)
      4 => string '6' (length=1)
  1 => 
    array
      1 => string '1' (length=1)
      2 => string '5' (length=1)
      3 => string '6' (length=1)
  2 => 
    array
      1 => string '1' (length=1)
      2 => string '11' (length=2)
  3 => 
    array
      1 => string '12' (length=2)

使用する機能

function extractList($array, &$list, $temp = array()) {
    if (count($temp) > 0 && ! in_array($temp, $list))
        $list[] = $temp;
    for($i = 0; $i < sizeof($array); $i ++) {
        $copy = $array;
        $elem = array_splice($copy, $i, 1);
        if (sizeof($copy) > 0) {
            $add = array_merge($temp, array($elem[0]));
            sort($add);
            extractList($copy, $list, $add);
        } else {
            $add = array_merge($temp, array($elem[0]));
            sort($add);
            if (! in_array($temp, $list)) {
                $list[] = $add;
            }
        }
    }
}
于 2012-10-11T11:20:14.707 に答える
5

問題はNP困難です。合計が目的の数になる問題のサブセットがあるかどうかを判断することでさえ、NP困難（サブセット和問題として知られています）であり、それに対する既知の多項式解はありません。

したがって、バックトラックなどの指数関数的な解決策を探す必要があります。考えられるすべての組み合わせを生成し、それらが有効かどうかを確認します。

トリミングを使用して検索を高速化できます（たとえば、合計13の部分サブセットを生成する場合、このサブセットのスーパーセットである他のサブセットをチェックする必要はありません。これらは明らかに解決策につながらないためです。

擬似コード：

findValidSubsets(sum,arr,idx,currSolution):
   if (sum == 0):
       print currSolution
   if (sum < 0): //trim the search, it won't be succesful
       return
   //one possibility: don't take the current candidate
   findPermutations(sum,arr,idx+1,currSolution) 

   //second poassibility: take the current candidate
   currSolution.add(arr[idx])
   findPermutations(sum-arr[idx],arr,idx+1,currSolution)

   //clean up before returning: 
   currSolution.removeLast()

複雑さはO(2^n)-最悪の場合、すべての2 ^ n個の可能なサブセットを生成する必要があります
。findValidSubsets(desiredSum,myArray,0,[])ここ[]で、は空の初期リストです。

于 2012-10-11T10:32:34.810 に答える
2

動的計画法を使用すると、ソリューションを次のように表現できます

solver(sum,start_index)
     stop_condition_here_when sum <= 0

     r=0
     for  i=start_index ; i < last_iddex :
            r += solver(sum - array[i],i+1)
            r += solver(sum ,i+1)
     return r

また、余分なメモを追加すると、このプログラムも高速化されます

于 2012-10-11T10:56:23.300 に答える
0

セットの長さを繰り返すことができます。各ステップで、 length のすべてのサブセットをチェックしますk。

for k = 1 to size(input):
    foreach permutation p of length k:
        if sum(p) == 12:
            bam!
于 2012-10-11T10:28:28.030 に答える