タイトル : Re^11: 組み合わせ合計検索 つづき 投稿日 : 2023/08/30(Wed) 13:18 投稿者 : 魔界の仮面弁士
> 'Console.Write("設定値:{0} ", 設定値) 出力方法を MsgBox に変えたいのであれば、 Sub 探索(…) を Function 探索(…) As String に変更し、戻り値で結果を返すようにした方が良いでしょう。 そうすれば呼び出し元は Label1.Text = 探索(1230, 値一覧3) MsgBox( 探索(1230, 値一覧3) ) Debug.WriteLine( 探索(1230, 値一覧3) ) のように、任意の方法で結果を確認できるようになります。 > これを10個以下で詳細値を求めたいと思っています。 No.12102 の実装において、FindCombination 時の再起処理のところで、 Node の階層数が 10 を超過したら探索を打ち切るようにすれば良いでしょう。 探索結果は Node で保持しているので、アイテム数も Node に管理させた方が手っ取り早いです。 たとえば Node クラスに Public ReadOnly Property Depth As Integer Get Return If(Parent Is Nothing, 0, Parent.Depth + 1) End Get End Property を追加しておいて、 If nextNode.Total <= targetValue Then の部分を If nextNode.Total <= targetValue AndAlso nextNode.Depth <= 10 Then に変更するとか。 これにより 合計値:1230 詳細値:36, 40, 45, 51, 55, 65, 69, 76, 82, 98, 106, 108, 115, 119, 165 が 合計値:1230 詳細値:36, 40, 45, 119, 133, 159, 163, 165, 184, 186 に変化します。アイテム数が 15 個から 10 個に削減されていますね。 実際には、最短で 8 個の組み合わせもありますが(106, 119, 148, 159, 163, 165, 184, 186)、 No.12102 の実装は「最初に発見したところで調査を打ち切る」実装になっているため、このケースでは 10 個の組み合わせ(36, 40, 45, 119, 133, 159, 163, 165, 184, 186)が先に出力されます。 よりアイテム数の少ない組み合わせを優先したい場合は、既に提供済みの すべての組み合わせを返すバージョンを使うなどしてみてください。 > 以下のように変更した場合 > msgbox の値は以下のようになります。 修正したコードにある、第 3 引数「ByVal kyoyouti As Integer」が謎です。 ここに値を渡している箇所も無ければ、引数値を読み取っている箇所すら見当たりません。 仮変数の名前から "許容値" の意味であることは想像ができますが、 実引数を見ても第 3 引数が指定されていないですよ? > 探索(1230, 値一覧3) > 一回目:8 > 二回目:15 今はラムダ式の中で、 MsgBox(a) として、変数 a の値を表示しているだけですよね。 探索結果を表示しないと意味が無いでしょう。 探索結果を格納しているのは Node クラスで、組み合わせを階層構造で保持していますので、 探索後に、Node クラスの中身を調べるようにしてください。 その特性上、幹側から枝側を辿るのではなく、枝側から幹側へ辿る設計です。 なお、たけしさんが書かれた「Dim a As Integer = 0」のカウントアップは、 詳細値の数を意味していないので、実装として間違っています。これについては後述。 > 以下のように表示させるにはどうすればよかったでしょうか。 探索終了時に、edge 変数(あるいは nextNode) の Parent を Do ループで辿れば良いのです。 たとえば 1, 2, 3, 4 の4 つの数値のすべての組み合わせから合計値 5 を探索する場合、 探索(5, New Integer() {1, 2, 3, 4}) の呼び出しにより、Dim root As Node に対して下記の構造が格納されます。 root ┣Value=1 … 1 = 1 ┃┣Value=2 … 3 = 1 + 2 ┃┣Value=3 … 6 = 1 + 2 + 3 ┃┗Value=4 … 5 = 1 + 4 ※このノードが edge 変数になる ┣Value=2 … 2 = 2 ┣Value=3 … 2 = 3 ┗Value=4 … 2 = 4 この場合の edge は、2 階層の深さになっているので edge.Value + edge.Parent.Value によって、4 + 1 = 5 という組み合わせを得られます。 |