0

動的計画法の典型的な質問があります。

私の質問には配列 = {1,2,3,4,5,6} が与えられます。合計が最大 k であるすべての配列を見つける必要があります。すべての集合を考慮すると、指数アルゴリズムになります。これを動的計画法で実現することを考えました。

Suppose f k =7,
My idea is 
Pass 1: {1],{2}....{6}
Pass 2: Pass1 + {1,2},{1,3},{1,4},{1,5}
Pass 3: Pass2 + {1,2,3},

そして、私のアルゴリズムは停止します。

これを動的計画法で定式化することはできません。入力はありますか?? このアルゴをプログラムにどのように定式化するのですか?

4

2 に答える 2

1

問題の DP ソリューションは、次の再帰式に従い、ボトムアップで構築する必要があります。

f(i,0) = {{}} //a set containing only an empty set
f(0,W) = {{}} (W > 0)
f(0,W) = {} (W < 0) //an empty set
f(i,W) = f(i-1,W) [union] extend(f(i-1,w-element[i]),element[i])

関数 extend(set,e) は次のとおりです。

extend(set,e):
   for each s in set: //s is a set itself
      s.add(e)

生成されるセットの数は指数関数的であり、DP テーブルに格納されるため、複雑さは依然として指数関数的である可能性があることに注意してください (疑似多項式でさえありません)。

于 2013-08-09T11:12:02.527 に答える
0

あなたの問題は、関連する決定問題がNP完全であることが知られているナップザック問題のインスタンスです。これは、ほとんどの場合、準指数アルゴリズムが存在しないことを意味します (ただし、数学的な証明はありません)。

ZachLangleys のコメントは、出力の生成には既に指数時間が必要であるため、効率的な問題解決ツールがあったとしても、すべてのソリューションの列挙は最悪の場合でも指数関数的であることを示しています。

決定問題はNP完全であるため、カウントは簡単ではありません（そうでなければ、カウントしてから、結果が0に等しいかどうかをテストします）。

于 2013-08-09T11:07:35.897 に答える