範囲内の合計でサブセットを見つける

Question

配列の要素の合計が所定の範囲内にある場合、どうすればその部分集合を見つけることができますか？例えば

：

let a = [ 1, 1, 3, 6, 7, 50] 
let b = getSubsetSumRange(3, 5) 

ので、Bは、潜在的に[3]、[1,3]、[3,1]、[3、1、1]とすることができます。私はそれらのうちの1つだけを必要とする順序は関係ありません。

Answer 1

この問題を解決するには、動的プログラミングアプローチを使用することをお勧めします。

は、彼らの合計がJに等しくなるように、元のサブセットa[1..i]から番号のうち、いくつかの数字を選択することが可能である場合F[i][j]は値trueてみましょう。

iは明らか1からaの長さに変化し、0からmaxはあなたの指定された範囲から第二の数で包括maxへjう。

F[i][0] = trueすべてi（常に空のサブセットを選択できます）。

その後F[i][j] = F[i - 1][j - a[i]] | F[i - 1][j]

論理的に、それはあなたが要素1..i-1から合計jとのサブセットを選択することができれば、あなたは明らかにサブセット1..iでそれを行うことができ、あなたが要素から合計j - a[i]とのサブセットを選択することができるかどうかということ1..i-1を入力し、そのサブセットに新しい要素a[i]を追加することで、希望の合計jを得ることができます。

あなたがFの値を計算した後、ご希望の範囲にある値jためtrueある任意のF[n][j]見つけることができます。

あなたがこのような番号kを見つけたとします。次に、必要なセットを見つけるアルゴリズムは、次のようになります。

for i = n..1: 
    if F[i - 1][k - a[i]] == True then 
     output a[i] to the answer 
     k -= a[i] 
     if k == 0 
      break