爲什麼要解決揹包問題。不被視爲線性編程？

Question

儘管揹包問題陳述似乎與線性規劃中的問題類似，但爲什麼不把揹包問題包含在線性規劃算法的類別下？

Answer 1

揹包可以寫成整數線性規劃程序。與一般的線性規劃不同，這個問題要求解決方案中的變量是整數。已知線性規劃在多項式時間是可解的，而整數線性規劃是NP完全的。

讀者練習：顯示3SAT可以簡化爲整數線性規劃。問題：MAX-3SAT（我們希望最大化滿意子句數量的3SAT變體）存在近似算法。首先你寫一個整數線性程序MAX-3SAT。然後，你放鬆它去線性化程序，通過刪除整數限制。然後，你用多項式時間求解線性程序。最後，給定的實X _我∈[0,1]，將它們舍入到整數，或產生隨機整數解y _我其中y _我 = 1的概率爲x _我。