背包问题笔记01

背包问题简介
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

背包问题思路
核心：动态规划

理解方式： 状态转移

思路（状态转移方程）：

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

思路详解：

若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1 件物品的问题。

如果不放第i件物品，那么问题转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前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