algorithm - 部分和問題の興味深いバリエーション

Question

部分和問題の興味深いバリエーションを、職場の友人から教えてもらいました。

サイズ n の正の整数の集合 S と、整数 a および K が与えられた場合、(集合 S の) 部分集合 R のうち、要素 を正確に含み、その合計が K に等しいものはありますか?

彼は、これは時間計算量 O(nka) で実行できると主張していますが、私はこの実行時間を達成する動的計画法のアルゴリズムを思いつくことができませんでした。それはできますか？

Answer 1

kとaが十分に小さい場合に実行できるため、配列を宣言できます

bool found[a][k]

Sの各値を反復処理し、見つかった配列のすべての状態を反復処理して、新しい状態を取得します。

たとえば、a=1およびk=7のインデックスで、Sからの現在の値が7であるとします。

found [1] [7]が真の場合、found[2][14]も真であることを確認できます。

反復が終了したら、[a][k]が真であるかどうかを確認するだけです。

Answer 2

S = {s1,\ldots,sn} とする

s1,\ldots,sj の中に合計が K になる要素を見つけることができる場合、P(j,K,a) を true とします。

次に、P(j,K,a) = P(j-1, K-sj, a-1) OR P(j, K, a) (sj が必要か不要か)。

次に、このアルゴリズムは、次元 n × K+1 × a+1 の 3 次元テーブルに記入することで構成されます。各エントリが満たされるまで一定の時間がかかるため、時間 (および空間) の複雑さは O(nKa) です。