0

部分和問題を学んでいたので、ここで質問したいのですが

（1）サブセット和アルゴリズム

このリンクのCコードを今読んだのですが、なぜ作者が定義できるのでしょうか。

S[i,0]=true ,S[0,j]=false

S[i,0]subset[1,...i]合計すると、0なぜ割り当てられるtrueのでしょうか。サブセットのコンテンツを出力する場合、このアルゴリズムを変更するにはどうすればよいですか。著者と個人的にチャットすることは禁じられているようだったので、投稿する必要があります。

S[i,0]（2）配列に負の数がある場合、それが適合しないことをテストしようとしました。との初期値を定義するにはどうすればよいS[0,j]ですか？

誰かが私が明確にするのを手伝ってもらえますか？

前もって感謝します！

4

1 に答える 1

1

base 句のSuggested には問題がありs[n,0]ます。これを使用すると、初期値としても取ることができるからです。

サブセット合計の再帰式に対するより適切な停止句は ですs[i,xi] = true。アイデアは単純です。セット{x1,x2,...,xi}にはサブセットが含まれており、合計するとxiサブセットになり{xi}ます。再帰は後で残りを処理し、合計が 0 になるサブセットがあれば、それを見つけます。

このアプローチによると、基本節は次のとおりです。

s[i,xi] = true (for each i)
s[0,j] = false (for each j)

そして、再帰式は次のとおりです。

s[i,j] = s[i-1,j] OR s[i-1,j-xi]

サブセットに実際に含まれる要素を取得するには、動的計画法で作成した行列に従う必要があります。行列によって行われる選択を「たどり」、「停止句」が見つかるまで true を生成するパスに固執します (s == xi)

次のように再帰的に記述できます。

getSubset(i,s):
   if s[i-1,s]: //there is a solution without choosing xi
       return getSubset(i-1, s)
   if (xi == s): //true base clause
        l <- new list
        l.append(xi)
        return l
   if s[i -1, s-xi]: //there is a solution when choosing xi
        l <- getSubset(i-1,s-xi)
        l.append(xi)
        return l

それはよく似ています (理由を理解していることを確認してください): How to find which elements are in the bag, using Knapsack Algorithm [and not just the bag's value]?

于 2013-01-03T17:06:05.037 に答える