これらの質問に続いて、サブセット和問題 と固定サブセットサイズのサムサブセットは、正確にk個の整数、k<=nを使用することを余儀なくされるサブセット和問題を解くための一般的なアルゴリズムは何か疑問に思いました。
Evgeny Kluevは、k = 4に最適を使用し、その後、k-4にブルートフォースアプローチを使用し、残りに最適を使用すると述べました。ここでブルートフォースアプローチと最適なk=4アルゴを組み合わせることで、彼が何を意味するのかを誰もが理解できますか？
おそらく誰かがより良い、一般的な解決策を知っていますか？
元の動的計画法アルゴリズムが適用されますが、わずかに拡張されています。部分的な合計を記憶することに加えて、合計を取得するために使用されるintの数も記憶する必要があります。
元のアルゴリズムでは、ターゲットの合計がMであり、n整数があると仮定して、ブールnxM配列Aを入力します。ここで、最初のintから（任意の数の）を選択することで合計を達成できるA[i,m]場合はtrueです（0からのインデックス付けを想定）。mi+1
これを3次元配列xxに拡張できますn。これは、同様のプロパティを持ちます。これは、最初のintから正確に選択することで合計が得られるM場合に当てはまります。kA[i,m,l]mli+1
intsが配列にあると仮定しますj[0..n-1]：
漸化式は非常に似ています-フィールドA[0,j[0],1] はtrue（選択、 1 int（duh）でj[0]合計を取得）、他のフィールドはfalse、 fromからのフィールドの派生も元のアルゴリズムと同様です：trueの場合はtrue（if最初のintから選択でき、次に明らかに最初のintから選択できます）またはtrueの場合（選択した場合は、合計を1増やし、intの数を1増やします）。j[0]A[0,*,*]A[i+1,*,*]A[i,*,*]A[i+1,m,l]A[i,m,l]mimi+1A[i, m - j[i+1], l-1]j[i+1]j[i+1]
が小さい場合は、明らかに上記の部分をすべてスキップして、 intkのすべての組み合わせを繰り返し処理し、それらの合計を確認するのが理にかなっています。確かに賢明なしきい値のようです。kk<=4