背包問題簡介
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

背包問題思路
核心：動態(tài)規(guī)劃

理解方式： 狀態(tài)轉(zhuǎn)移

思路（狀態(tài)轉(zhuǎn)移方程）：

f[i][v] = max{ f[i-1][v] , f[i-1][v-c[i]]+w[i] }

思路詳解：

若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i-1 件物品的問題。

如果不放第i件物品，那么問題轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]

解題過程：

 int valueMax(int i, int v)
 {
    if (i == 0 && Cargo[0] < v)return Cargo[0];

    if (i == 0 && Cargo[0] > v)return 0;

    if (Cargo[i] > v) 
         return valueMax(i - 1, v);

    if (Cargo[i] < v)
         return max(valueMax(i - 1, v), valueMax(i - 1, v - Cargo[i]) + Cargo[i]);
  }

參考資料：http://blog.sina.com.cn/s/blog_8cf6e8d90100zldn.html