セットパーティション化に関する問題

Question

$ a_j={（a ^ i_j、b ^ i_j）〜：~0 \ leq i \ leq n、\ text {および} a ^ i_j、b ^i_J \ in \ mathbb {z} ^ + \} $

与えられたセット $ A_1、\ Ldots、A_ {P} $ 、正の整数 $ k $ 、問題は、存在するかどうかを確認することです。 $ \ sum_ {j} ^ {} ^ {i_j} _j \ geq k $ と $ \ sum_ {j} ^ {i_j} _j \ geq k $ 。

問題が設定されたパーティション上の問題に関連しているように見えますが、セット分割の問題から削減する方法はわかりません。誰かがこの問題を解決するためのアルゴリズムを見つけるのを助けますか？

Answer 1

$ opt [t、x] $ の最大値 $ \ sum_ {j= 1}の最大値です。 1つの要素 $（a_j ^ {i_j}、a_j ^ {i_j}）$ を選択することによって達成することができるt b_j ^ {i_j} $ 最初の $ t $ の $ \ sum_ {j= 1} ^ i a_j ^ {i_j} \ ge x $ 。 制約を満たすことができない場合は、 $ opt [t、x]= - \ infty $ 。

上記の定義によると、 $ opt [0,0]= 0 $ と $ OPT [0、 $ x> 0 $ の場合x]= - \ infty $ 。

$ t> 0 $ の場合は： $$ OPT [T、X]=max_ {i= 1、\ dots、n} \ left（b_t ^ i + opt [t-1、\ max \ {x-a_t ^ i、0 \}] \ right）。 $$

問題への回答は、 $ opt [p、k] \ ge k $ の場合に限り "yes"です。

$ O（p \ cdot k）$ サブ問題があり、それぞれが $ oで解決できます。 （n）$ 時間、このアルゴリズムの全体的な時間の複雑さは $ O（p \ cdot k \ cdot n）$ です。

あなたの問題がNP-HARDであることを示すために、それがパーティションの問題の一般化であることに気付くことができます.set $ s={x_1、\ dots、x_m \ $ $ m $ 負の整数では、サブセットがあるかどうかを決定します。 $ s '$ < / SPAN CLASS="math-container"> $ s $ の/ span $ s $ の。

これを見るために、 $ n= 2 $ 、 $ p= m $ 、 $ A_J={（x_j、0）、（0、x_j）\} $ 、および $ k=frac {1 {2} \ sum_ {x \ in} x $ 。