algorithm - ナップザック問題を解くことが線形計画法とみなされないのはなぜですか?

Question

ナップザック問題のステートメントが線形計画法の問題に似ているように見えるにもかかわらず、ナップザック問題が線形計画法アルゴリズムのカテゴリに含まれないのはなぜですか?

Answer 1

Knapsack は、整数線形計画法プログラムとして記述できます。通常の線形計画法とは異なり、この問題では解の変数が整数である必要があります。線形計画法は多項式時間で解けることが知られていますが、整数線形計画法は NP 完全です。

読者の演習: 3SAT を整数線形計画法に還元できることを示してください。

豆知識: MAX-3SAT (満たされる節の数を最大化する 3SAT の変形) などの問題に対する近似アルゴリズムがあります。まず、MAX-3SAT を整数線形プログラムとして記述します。次に、整数制限を削除して、線形計画法に緩和します。次に、線形計画法を多項式時間で解きます。最後に、実数 x _{i ∈ [0,1] が与えられた場合、それらを整数に丸めるか、y i} = 1の確率が x i である_ランダムな整数解 y _iを生成します。