背包問題是一種組合優化的 NP 完全問題。 給定一組物品，每種物品都有自己的價格與重量；在限定的總重量內，如何選擇才能使總價值最高？ 問題名稱來自「如何選擇最合適的物品放進背包」。此問題常見於商業、組合數學、密碼學與應用數學領域。 也可描述為決定性問題：在總重量不超過 W 的前提下，總價值是否能達到 V？
背包問題的常見變形如下：