2 つの配列 a と b があり、それぞれに n 個の数値が含まれています。あなたは数 k を持っています。
[n] = インデックス セット 1...n
[n] のサブセット S を見つけて、a で S によってインデックス付けされた要素の合計が少なくとも k になり、b で S によってインデックス付けされた要素の合計が可能な限り小さくなるようにします。
このための多項式時間アルゴリズムさえ見つけることができません。これを解決する方法についてのアイデアに感謝します。
質問する
462 次
2 に答える
0
少なくとも多項式に興味がありますよね？セットのすべてのマスクを指数関数的に反復し、両方の条件をチェックするのは簡単です (合計 >= k で、b と現在の合計で以前にあったものを比較します)。
于 2012-07-31T17:55:38.867 に答える
0
この問題の一般的な解決策は NP 完全です。これは、ナップザック問題を包含するためです。ただし、ナップザックの問題と同様に、動的計画法を使用して建設的に (「疑似多項式時間」で) 対処できる場合があります。
Tこれを確認するには: ナップザック サイズと オブジェクト サイズのナップザック問題が与えられた場合c[i]、質問で説明されているようにa[i]==b[i]==c[i]とのような問題を作成しますk == sum(c[i]) - T。
次に、ナップザック問題の解は、 にない一連のインデックスですS。
sum(c[i] *not* indexed by S) == sum(c[i]) - sum(a[i] indexed by S)
T == sum(c[i]) - k
問題の制約が成り立つ場合にのみ、Sナップザックの制約を満たすことに注意してください。sum(c[i] *not* indexed by S) <= Tsum(a[i] indexed by S) >= k
sum(c[i] *not* indexed by S) == sum(c[i]) - sum(b[i] indexed by S)
提起された問題の解は、有効な S で最小化sum(b[i] indexed by S)され、有効な S でsum(c[i] *not* indexed by S)最大化されるため、ナップザック問題の最適解です。
于 2012-07-31T19:29:05.793 に答える