0

次のような問題があります。

一連の数値 (S)、初期値 (V)、および目標値 (T) が与えられた場合、一連の + 操作と - 操作がシーケンス S に割り当てられるかどうかを確認します (操作はシーケンスの順序を尊重する必要があります)。 ) V から開始して、T 以上の数に到達します。また、いつでも破ることができない制限 X があります (合計がいつでも間隔 [0, X] を出る場合、その解パスは無効です。問題のすべての数値もこの間隔内にあります)。

また、制限ルールを尊重して、これらの操作から取得できる最大の合計を見つける必要があります (-last- 操作で合計が制限を超えると、ルールが破られる可能性があります)。

私はそれを調べて、ナップザックの問題とパーティションの問題に対する動的プログラミングの解決策について少し調べましたが、解決策はこの行にあると思います。

ただし、制限ルールを処理する方法と、最大の合計を見つける方法がわかりません。制限の問題は、いくつかの状況で発生します: 足し算され、残りの数が引かれることになる数を見つけるためのナップザックの解を見つけようとするとします。ナップザック ソリューションは合計の上限を破る可能性がありますが、操作の順序が原因で実際​​の合計が破れない可能性があります (制限が実際に破られる前に何かを減算する可能性があり、その後は破られません)。全て）。

これに対する良いアプローチを見つけるのを手伝ってくれる人はいますか? ありがとうございました。

4

1 に答える 1

1

この問題は分割問題のバリエーションであり、1 つのセットは追加する要素であり、もう 1 つのセットは減算する要素です。

可能な解決策は、当然のことながら、分割問題の疑似多項式の解決策に基づいています。

D(V,0) = true
D(s,0) = false     s != V
D(s,i) = false    s<0 or s > X
D(s,i) = D(s-arr[i],i-1) OR D(s+arr[i],i-1)

再帰関係を効率的に計算し、サイズ の DP テーブルを作成できます(X+1)*(n+1)。 完了すると、次のようなテーブル内
の最大値を探します。T<=s<=XD(s,n) == true

于 2015-07-02T12:17:03.390 に答える