組合せ

質問

1から　i番目まで、数字がランダムに並んでいます。（マイナス数値からプラス数値まで）。
これらの数値の組合せで、組合せの合計値が、ある目標値になる組合せのすべてを発見して、その組合せを1からiの番号で表示したいのです。
目標値は一個だけ定めます。
どのような論理を組めば可能でしょうか。（この論理をエクセルソフトに組み込み計算します）。

回答No.8

stomachman

数の列 list[i] (i=1,2,.....,L)が与えられている。この中から任意の個数の要素を選んで、その総和が目標値Tになるようにしたい。そのような選び方を全部示せ。

結局の所総当たりで調べるしかなさそう（NP問題）ですが、無駄な探索を省くと少しは速くなります。そのためには
・値をsortしておく
ことによって、見込みのない探索を早く打ち切ることができます。それから、
・値が0である要素は、加えても加えなくても合計値は変わらない。
・同じ値が複数個入っている場合も、その取捨選択の組み合わせを変えたところで合計値は変わらない。しかし幾つ選択できるかは、個数による。
これらを考慮しないと無駄な探索をやってしまうことになります。なお
・正の値と負の値は区別して扱う必要がある。これが問題を難しくしている。（もしlistに正の値しか現れないというのだと、だいぶすっきりしたものになる。）
というのも重要な点です。
これらを盛り込んでみると、以下の通り。

あらかじめlistを値が小さい順にsortする。ただし、値が0の要素は除外する。その結果をV[j](j=1,...,N)とする。（N≦L。L-Nはlistに含まれていた0の個数である。）すると、以下の性質が成り立つ。
∀j∀k(1≦j<k≦N → V[j]≦V[k])
∀j(1≦j≦N →V[j] ≠0)
目標値Tを与えたとき、解は（もしあれば）自然数の集合Xで表され、
T= Σ{x∈X} V[x] （Σ{x∈X}V[x]とは、Xに含まれる全ての要素xについてV[x]の総和を取ることを示す。）
を満たす。
この準備をした上で、Solve(T)を走らせればOK。

Solve(T):
T:目標値
if T=0 then
　makeAllAnswer(φ) （空集合φは一つの解である。この解に随伴する全ての答を生成する。詳細は後述。）
else
　wp := Σ{j=1～N} max(0,V[j])　　　（max(a,b)はa,bの内の大きい方）
　wn := Σ{j=1～N} min(0,V[j])　　　（min(a,b)はa,bの内の小さい方）
　if T>wp then （Tが大きすぎて解がない）
　　exit
　fi
　if T<wn then （Tが小さすぎて解がない）
　　exit
　fi
　search(φ,T,wp,wn,0) （φは空集合。）
fi
end.

search(X,T,wp,wn,maxX):
（数の列Vの中から、既にいくつかの数が合計に入れる物として選択されている。その番号の集合がXである。Tは、元々の目標値からこれらの「すでに選択されている要素」の合計値　Σ{x∈X} V[x] を差し引いた物である。wpはXに幾つか要素を追加して作ることが可能な最大値、wnはXに幾つか要素を追加して作ることが可能な最小値を表す。Xは解ではなく、しかも、Xに（maxXより大きい）要素を幾つか追加すれば解になる可能性がある。searchは実際にXに要素を追加して、解を探す。）
X: 自然数の集合。Vのうち、すでに選択されている要素の番号を表す
T: 目標値（ただし、すでに選択されている要素の合計は差し引かれている）
wp: Xの最大値より大きい数nについてV[n]のうち、正の値のものの合計
wn: Xの最大値より大きい数nについてV[n]のうち、負の値のものの合計
maxX :集合Xの要素の内の最大のもの（ただしX=φのときはmaxX=0）

（まず、あと１個の要素を加えたら解になるかどうかを調べる。加える要素KはmaxX+1～Nのうちのひとつであるから、２分法を使って探索すると速い。解がない場合にはk=0を返すものとする。）
binarySearch(T,maxX+1,N,k)
if k>0 then　(X∪{k}は解である。）
　makeAllAnswer(X∪{k})（解X∪{k}に随伴する全ての解を生成する。）
　more := false （解が見つかったので、同じXについてこれ以上探しても見込みはない）
else
　oldVk:=V[maxX+1]-1（右辺はV[maxX+1]と等しくない値なら何でも良い。）
　k:=maxX
　more:= true　（ループを制御するフラッグ）
　repeat
　　repeat
　　　k:=k+1（Xに追加する要素をkとする。kを増やしながら探す）
　　until (k>N) or (V(k)≠oldVk) （V[k]が前回のループと同じであるkは調べても無駄なので飛ばす）
　　more := (k≦N)
　　if more then （Xについてまだ調べ尽くしていない。）
　　　possible:= true （Xに要素を追加して調べるかどうかを制御するフラッグ）
　　　if V[k]<0 then
　　　　if T>wp+V[k] then（X∪{k}に対してTは大きすぎるが、kを増やせばまだ可能性はある。）
　　　　　possible = false
　　　　elseif T<wn then（X∪{k}に対してTは小さすぎる。つまり、X∪{k}に追加できる全ての負の値を合わせてもまだTの方が小さい。これ以上探しても見込みはない）
　　　　　possible = false
　　　　　more := false
　　　　fi
　　　　wn:=wn-V[k]
　　　else （V[k]>0の時）
　　　　if T>wp then（X∪{k}に対してTは大きすぎる。つまり、X∪{k}に追加できる全ての正の値を合わせてもまだTの方が大きい。これ以上探しても見込みはない）
　　　　　possible := false
　　　　　more := false
　　　　elseif T<V[k] then（X∪{k}に対してTは小さすぎる。X∪{k}だけでTを越えてしまった。このうえkを増やせばV[k]も増えるから、これ以上探しても見込みはない）
　　　　　possible := false
　　　　　more := false
　　　　fi
　　　　wp:=wp-V[k]
　　　fi
　　　if possible then（X∪{k}は解ではないが、これに対してTは大き過ぎも小さ過ぎもしない。要素を追加して探してみる必要あり。）
　　　　search(X∪{k},T-V[k],wp,wn,k)　（kを、「既に選択されている要素」に加えて調べる。）
　　　fi
　　fi
　until not more （Xについて調べ尽くすまで繰り返す。）
fi
end.

binarySearch(L,U,T,k):
（あと１個の要素を追加すれば解があるのかどうかを２分法で調べる。）
if L>U then
　k:=0
　exit
else
　k:= round((L+U)/2)（LとUの真ん中ぐらいの値を作る。）
　if T=V[k] then（解が見つかった）
　　exit
　elseif T>V[k] then
　　binarySearch(k+1,U,T,j)
　　k:=j
　　exit
　else （T<V[k]）
　　binarySearch(L,k-1,T,j)
　　k:=j
　　exit
　fi
fi
end.

makeAllAnswer(X):
（解Xに随伴する全ての答を作り出す。
　実際に欲しいのは解X（列Vの番号の集合）ではなく、それに対応する答（列listの番号の集合）である。
　もしlistの中に0がなく、しかも同じ値が複数個入っていることもないのであれば、単にXの各要素に対応するlistの要素の番号を書き出せば良いだけのことである。しかしそうなっているとは限らない。
　「解Xに随伴する答」とは、Xに含まれない自然数1≦y≦Nで、Xのどれかの要素xと値が同じであるもの（V[y]=V[x]）が存在する場合、これをxと入れ替えた物を別の解として、それに対応する答のことを言う。さらに値が0であるようなlistの要素を何個か加えたものも、解Xに随伴する答である。
　要領よく計算するためには、あらかじめlistから重複を除いた列 ulist[m] (m=0,1,2,....,M.ただしulist[0]=0とする。)を作り、Q[m]={i| list[i]=ulist[m]}, nQ[m]=（Q[m]の要素の数）という表を作っておく。さらに列Vの番号xと列ulistの番号mとの対応表emを作っておく。すなわちulist[em[x]]=V[x]となるようにem[x]を用意しておく。すると、具体的に解Xが得られたとき、）
X:解
for m=1～M
　nP[m]:=0
rof
for each x∈X
　nP[em[x]]:=nP[em[x]]+1
rof
によって、nP[m]は、V[x]=ulist[m]であるようなx（∈X）の個数を表すことになる。勿論0≦nP[m]≦nQ[m]である。
nP[m]=0の場合、Q[m]の要素は解には含まれない。従ってQ[m]について選択の余地はない。
nP[m]=nQ[m]の場合、Q[m]の要素は全部解に含まれ、従ってQ[m]について選択の余地はない。
0<nP[m]<nQ[m]の場合、Q[m]について選択ができ、Q[m]の要素の内からnP[m]個の要素を選ぶ選び方は (nQ[m])! / ((nP[m])!(nQ[m]-nP[m])!)通りある。
0<nP[m]<nQ[m]であるような全てのmについて、それぞれ独立に (nQ[m])! / ((nP[m])!(nQ[m]-nP[m])!)通りの選び方ができ、さらに、nQ[0]個以下の0をこれに加えるやり方は2^(nQ[0])通りある。だから全部で
（2^(nQ[0])）(Π{m=1～M) ((nQ[m])! / ((nP[m])!(nQ[m]-nP[m])!)))通りの「随伴する答」を作ることになる。（Π{m=1～M) f(m)はf(1)×f(2)×...×f(M)を表す。）
どうやってやるかは自明だしめんどくさいので書かない。
end.

以上、テストはやってませんから間違ってたらごめんね。