• 这种解法是把之前的二维解法压缩成一维解法
  • 二维数组的解法就是不断把上一层向数组经过运算加载到下一层的过程
  • 那么如果只在当前层不断修改数据，可以将数组减少为一维
  • 不断修正一维数组值，而且是以类似滚动一样的方式变化值，所以也叫滚动数组
• 动规五部曲
  • dp数组（一维）含义：容量为i背包所能容纳的最大价值
  • 递推公式：dp[i] = std::max(dp[i], dp[i - wight[j]] + cost[j])
    • 注意这其中的i与j的含义不同
  • dp数组初始化：
    • 如果考虑没有物品作为第一行数据，所有一维值都是0
    • 如果考虑第一个物品作为第一行数据，数据在这个背包容量之后都为第一个物品的价值，而之前容量都是0
      • 因为递推公式中要跟自身比较取最大值，所以初始化时，只要是非负的最小值即可，即为0
  • 遍历顺序
    • 要倒序遍历这个一维数组，这其中的原因是由于递推公式决定的
    • 递推公式中有dp[i - weight[j]]，这其中wight[j]肯定是大于等于0的，也就是要到下标小于i数组中前面找出数据来更新i处的数据
    • 如果从前向后更新，就相当于修改了修改了二维数组中前一行数组的值，这样结果就会不准确，会导致同一物品可能会多次加入到背包中
    • 与二维数组不同的是，在双重遍历时，外层遍历一定是物品，内层遍历背包容量，这是因为如果这两个遍历颠倒过来，会导致内部循环结束后，一维数组的内容只剩下价值最大的一个物品，其它物品不能组合加入进去，而二维则可以随意颠倒内外循环
  • 打印
  • 汇总