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]?