Geek_Ling

摘要： 前言背包問題是一個經典的算法問題，可以用動態規劃，貪心法，分支界限法等方法解決問題描述：有n個物品，編號1,2,3，、、n，其中第 i 個物品重量為Wi 價值 Vi ，有一個容量為W的背包。在容量允許范圍內，如何選擇物品，可以得到最大的價值。（為了簡單起見，假設物品的重量 Wi 和價值Vi 都是正數）根據取物品的方式，背包問題又可以被分為三類：0/1背包問題(0-1 knapsack problem)這也是最常見的背包問題，對于每個物品，要么取走要么不取走，每個物品只能取一次。可以用數學表達式表示為：maximize subject to其中xi只能為1 或者0 所以稱為背包問題有界限的背包問 閱讀全文