私はいくつかの間隔I = {I(1), I(2), ..., I(m)}を与えましたI(i) = [a_i, b_i] (1<=a_i<=b_i<=n)。間隔が互いにカバーしていると思われるかもしれません (英語が下手で申し訳ありません) {[1,5], [3,6]}, {[2,5], [5,7]}。I{[1,1], [2,2], ..., [n,n]}に含まれている必要があります。
としましょうC(i) = b_i - a_i + 1。
{I(c_1), I(c_2), ..., I(c_k)}お互いに重なり合っていないものを見つけたいC(c_1) + C(c_2) + ... + C(c_k) = T. (1 <= T <= n).
Subset Sum問題を使用してDPソリューションを見つけることができO(n*T)ました.NPだと思いますが、よくわかりません。以上を最適化できますO(n*T)か?
この問題は、サブセット合計問題(一連の数値とターゲット数値が与えられた場合、このターゲットに合計されるサブセットがあるかどうかを調べます) から簡単な還元で還元できます。
サブセット合計のインスタンスが与えられた場合: - ポイントを使用して重複しない間隔、間隔 iS={c_1,c_2,..,c_n},Tを作成することにより、この問題のインスタンスを作成します(昇順で簡単に実行できます)。同じままです。nc_iT
ここで、部分和問題の答えは、合計が になる間隔の部分集合がある場合にのみ真になりTます。問題の定義により、すべての間隔が互いに重ならないため、基本的に同じ問題です。
このことから、あなたの問題はNP-Hardであると結論付けることができます。
さらに、問題を よりもうまく解決できればO(T*n)、同じアプローチを使用してサブセット和の問題をO(T*n)1,2よりもうまく解決できます。
ただし、私の知る限り、サブセットの合計に対する最適な疑似多項式の解はO(T*n)であるため、そのような解がある場合は、それに固執してください。
(1) 問題の変換はO(n)
(2) この主張は、この特定の簡約のみに当てはまり、多項式簡約の一般的な場合には当てはまりません。