4

Aに7個、Bに4個あるとします。

A=[10;40;90;130;200;260;320]
B=[100;300;500;1000]

可能な組み合わせのリストが欲しいのですが：

  • Aのすべてのサブコンポーネントを含める必要があります
  • Bのサブコンポーネントは、追加されたすべてのサブコンポーネントの合計が2000を超えるまで追加できます。

誰もがMatlabでこれを行う方法を知っていますか？

私の試み：

X=sum(A);
y=1;
for Y=1:((length(A))-1);
   X=X+B(y);
   if(X>2000)
       disp('Following is unacceptable')    
   end
   y=y+1
end

ただし、このコードは正しくありません。Bの最初の要素を追加し、次に2番目の要素を追加します。それは私に可能な組み合わせを提供していません。

例 ：

  • sum（A）+ B（1）= OK
  • sum（A）+ B（4）=OKではありません
  • sum（A）+ B（1）+ B（2）= OK
  • sum（A）+ B（2）+ B（3）= OK
  • 等...

将来、AまたはBの値が変更された場合に、これを自動化する必要があります。これが確率の場合でもあるかどうかはわかりません。

4

3 に答える 3

4

nchoosekとダブルループを使用して、次forの要素のすべての可能な組み合わせを調べますB。

SA = sum(A);
for k = 1:numel(B)
    for idx = nchoosek(1:numel(B), k)'
        B_subset = B(idx);
        if (SA + sum(B_subset) <= 2000)
            disp([A(:)', B_subset(:)'])
        end
    end
end

これにより、合計が2000未満（または等しい）のすべての組み合わせが出力されます。この例では、次のようになります。

    10    40    90   130   200   260   320   100
    10    40    90   130   200   260   320   300
    10    40    90   130   200   260   320   500
    10    40    90   130   200   260   320   100   300
    10    40    90   130   200   260   320   100   500
    10    40    90   130   200   260   320   300   500
    10    40    90   130   200   260   320   100   300   500

説明：

内側のforループ：
内側のforループはnchoosek(1:numel(B), k)、を使用します。これは、1 ... length（B）からすべてのk-lengthの組み合わせを生成します（習慣からではnumelなく使用lengthしています。この場合、同じ効果があります）。たとえば、この場合Bは4つの要素があるため、次のようk = 3になりますnchoosek(1:4, 3)。

    1   2   3
    1   2   4
    1   3   4
    2   3   4

これから得られるのは、の要素のインデックスのすべての可能なk長の組み合わせですB。各反復で、このforループはインデックスの異なる組み合わせをに割り当てますidx。Bのインデックスを実際の要素に変換するにはどうすればよいですか？単に書くだけB(idx)です。
ループ内で組み合わせがテストされます。合計sum(A) + sum(B(idx))が2000未満（または等しい）の場合、その組み合わせが表示されます。

外側のforループ：
外側のforループは、可能なすべての組み合わせの長さ（つまり、のすべての可能な値k）を単純に繰り返します。

お役に立てば幸いです。

PS：

将来のMATLABプログラミングのヒント：
1。変数名では大文字と小文字が区別されます。
2.ループ変数をインクリメントする必要はありません。ループはそれforを自動的に行います。

于 2012-11-20T22:47:39.040 に答える
2

Bがそれほど長くない（約10要素）と仮定すると、すべての組み合わせを徹底的に検索すると問題なく機能します。この徹底的な検索は再帰関数を使用して実行できますが、以下のコードは、MATLABで特に簡潔なトリックを使用しています。つまり、各組み合わせをバイナリビット文字列として表すことにより、Bの要素のすべての組み合わせをスイープします。

% examine each of 2^length(B) combinations
for i=0:2^length(B)-1
    % converts the binary string into an array of 0 and 1 used to select elements in B
    combo = dec2bin(i, length(B))-'0'; 
    % print the combination of elements if their sum is large
    if combo * B + sum(A) > 2000
       disp(find(combo));
    end
end

2 ^ length（B）の可能な組み合わせがあります。これにより、それらが順番に調べられ、組み合わせが長さlength（B）のバイナリ文字列として表され、これらの要素の合計が評価​​されます（ビット文字列とBの間に内積があります）。

于 2012-11-20T22:36:24.617 に答える
2

最善のアプローチには、次のような再帰が含まれます。

sumA=sum(A);
find_CombinationsOfB(B,sumA,[])

function ret=findCombinationsOfB(in_vals,total_sum,already_contained)

if total_sum>2000
    ret=false;
else
    for y=1:length(in_vals);
       if (~findCombinationsOfB(in_vals([1:(y-1);(y+1):length(in_vals)],total_sum+in_vals(y),[already_contained in_vals(y))
          display([already_contained in_vals])
       end
    end
    ret=true;
end

基本的に、これはBの各組み合わせを試行します。これは、Aからの合計を含め、合計が2000にならないものを出力します。

ステップバイステップで、これが何をするかです：

  1. 最初に、Aの合計とともにBの完全な配列が渡されます。これまでに使用されたBの要素を格納するために、空の配列が渡されます。
  2. 各要素が順番に関数に追加され、新しい合計で、配列に値がない状態で再度呼び出されます。
  3. いずれかの時点で配列の合計が2000を超えると、その推論の連鎖が停止します。

これがどのように機能するかについて詳しく知りたい場合は、次のように、関数の先頭にin_vals、total_sum、およびalready_containedを出力します。

fprintf("in_vals=%s   total_sum=%i   already_contained=%s",mat2str(in_vals),total_sum,mat2str(already_contained));

何が起こっているかを各反復で表示する必要があります。

于 2012-11-20T22:42:44.377 に答える