动规五部曲
dp数组的含义，注意这是一个二维数组。dp[i][j]- 第一维度代表“从0到第
i个物品，而且包括选或不选的情况，即这一维度代表物品编号 - 第二维度代表代表背包容量
- 合在一起的意思是当背包容量是
j时，从0到i个物品中选择任意物品的最大价值
- 第一维度代表“从0到第
- 递推公式：两种选择
- 第一是不选择物品
i，则当前最大值就是要从前i - 1个物品且容量为j的最大值 - 第二是选择当前物品
i，则最大值是i物品的价值，加上背包可以放下i物品重量时量大容量的最大价值 - 合并在一起写出来就是：
dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- 第一是不选择物品
- 初始化数组
- 增加一个什么物品都没有的行，可以列在所有物品行的最上面，这一行都可以上初始化为0
- 把第一列，即容量为0的列，都可以初始化成0
