背包DP
动态规划的经典应用-背包问题。
一般来说，就是给定一组有固定价值和固定重量的物品，以及一个承重量固定的背包，求在不超过背包最大承重的前提下，能放进背包里的物品的最大总价值。
动态规划（DP）类问题主要求解的步骤
1、划分阶段
2、确定状态
3、确定决策并写出转移方程式
贪心为什么错？
根本原因：贪心需要算性价比（单位重量的价值），但题中的物品不可分割，所以计算性价比来排序的策略是错的。
所以，可以考虑01搜索，对每个物品遍历“选 or 不选”两种情况，但是可能会超时。
背包问题分类：01背包，完全背包，多重背包，分组背包……
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 01背包
问题定义：有 n 件物品和一个容量为 v 的背包，第i件物品体积 wi ，价值 vi ，每件物品只有一件，只能选或不选，求不超过容量的前提下能获得的最大总价值
状态定义：
> dp[i][j] 表示前 i 个物品，容量为 j 时的最大价值
状态转移：
> 选第 i 件物品且容量够，则 dp[i][j] = dp[i - 1][j - w[i]] + v[i]
> 不选第 i 件物品，则 dp[i][j] = dp[i - 1][j]
> dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j])
答案：
> 一般来说，dp[n][m];
实现代码：
滚动数组优化：
每次都是覆盖上一行，尝试是否可以使用一维数组进行实现。
确定状态：dp[j] 表示背包容量为 j 时的最大价值。
