背包算法

例题分析->共同特性（理解重点）

有N件物品和一个容量为V的背包，第i件物品的费用是value[i]，价值是weight[i]，求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大？

经过分析，我总结出，这一类的问题都有一下共同特点（都能分析出三个值：“最大量”、“属性1”、“属性2”）：

1. 有一个最大量，本题中这个最大限制量是容量（当然也可以是其他量，比如说我还碰到的“体力值”）（而有时候这个最大量是隐性给出，就是物体的个数）

2. 进行操作的每一个单位有两个属性值，本题中分别是重量和价值

3. 2中所提及到的两个属性值，一个是用来和最大量进行比较，从而确定选取方案；另一个属性值是用来获取最值，比如说本题中的“价值总和最大”（这个属性值有时候是隐性给出的，例如只给出第一个属性，第二个属性值每一个物体默认是一样的）

通用的基础公式（理解重点）

定义**dp[i][j]**：表示前i个物品，在容量为j的时候，最佳方案所能得到的最大总价值。

1. 约束条件：weight[x1]+weight[x2]+…… < j（同时j<=V，该条件可以用来作为循环遍历的约束条件）
2. 通项公式：

   **dp[i][j] = dp[i-1][j]**，weight[i] > j时，

   **dp[i][j] = max{dp[i-1][j]，dp[i-1][j-weight[i] + value[i]}**，j >= weight[i]时

dp二维数组如下：