揹包問題

揹包問題或揹包問題是組合優化中的問題。給定一組具有權重和值的專案，確定要包括在集合中的每個專案的數量，使得總權重小於或等於給定限制，並且總值儘可能大。它的名字來源於受固定尺寸揹包約束的人所面臨的問題，必須用最有價值的物品填充它。

這個問題經常出現在有資金限制的資源分配中，並且在組合學 ，電腦科學 ，複雜性理論 ，密碼學 ，應用數學和日常幻想體育等領域進行研究 。

揹包問題已經研究了一個多世紀，早期作品的歷史可以追溯到 1897 年。揹包問題的名稱可以追溯到數學家 Tobias Dantzig （1884-1956） 的早期作品，並提到了常見的問題。包裝你的 mosty 有價值或有用的物品，而不會使你的行李超載。