动态规划之背包问题：组合优化中的经典NP挑战
背包问题概念：
背包问题是一种经典的组合优化的NP问题，在计算机科学、运筹学等领域有着广泛的应用。
问题可以简单的描述为：
假设有一个容量为C的背包和n个物品，每个物品i都有重量w[i]和价值v[i]。目标是选择一些物品放入背包，使得放入背包的物品总价值最大，同时背包中物品的总重量不能超过背包的容量。
这里先简单介绍两种背包问题：
1.01背包：也就是你物品的个数是1个，你拿了就剩0个，没拿就剩1个
2.完全背包：物品个数无数个，可以拿0/1/2/3/4至无穷多个
背包也可以分两种：1.背包不需要装满。2.背包必须装满
这样两两组合就有4种问题
其实背包问题还有很多种情况，个数有2/3/4/5等等，每个在X2（不必装满||必须装满）
这里重在了解01背包和完全背包问题（其他可能更多出现在竞赛中）
01背包问题是所有问题的基础（基本上所有的背包问题都衍生于01背包）
以牛客网例题为例（leetcode没有较好的入门例题）
题目解析：
第1小问：背包不必装满问题
第2小问：背包必装满问题
建议画一个表格，而且最好上面标号，就有点像我们之间处理初始化那里一样，多加一行多加一列，有利于我们后面填表
算法原理 ：
其实这里的背包问题就是一个线性dp问题，也就是你挑物品时可以从左往右依次选还是不选
类似于我们之前讲解线性dp问题一样去分析即可
1.状态表示：经验+题目要求
经验：以i位置为结尾巴拉巴拉
题目要求：dp[i]:表示以i位置为结尾（从前i个物品中）所有的选法中价值最大的
我们可以发现这个状态表示推导不出来状态转移方程，因为我们在考虑第i个物品的时候，需要考虑这个能不能放进背包，我连总的重量和剩余容量都不知道
所以我们需要改一下状态表示，既然一维表示不了，那我们就二维
dp[i][j]:从前i个物品挑选，总体积不超过j，所有选法中，能挑选出来的最大价值
为什么这里是不超过？因为我们做第一小问，问题是不需要装满
2.状态转移方程：以最近的一步状况，划分情况
1.不选i物品，不选的话是不是最大价值就在i-1前，回归我们的状态表示
dp[i-1][j]:从前i-1个物品挑选，总体积不超过j，所有选法中，能挑选出来的最大价值
那这种选法中dp[i][j]=dp[i-1][j]
2.选i物品，选的时候是不是要考虑能不能装进背包，所以我们需要判断背包剩余容量
剩余容量就是j-v[i]
如果剩余容量小于0，那这个i物品肯定是不能选的
如果剩余容量大于等于0，这个i物品就可以选，怎么选，回归状态表示
是不是你自身的价值加上i-1的最大价值
所以综上，最大价值就是这两种选法中最大的那个
第2小问讲解：
这里只需要稍加修改一下状态表示即可
原： dp[i][j]:从前i个物品挑选，总体积不超过j，所有选法中，能挑选出来的最大价值
现：dp[i][j]:从前i个物品挑选，总体积正好等于j，所有选法中，能挑选出来的最大价值
基本是一样的，但我们需要特别注意：我们用dp[i][j]=-1,表示没有这种情况，就是所有的选法无法凑到刚好总体积等于j的情况
那为什么不等于0呢？因为如果等于0，我们就无法区分dp[i][j]=0时表示什么情况，我们之前做第一问的时候就有初始化为0，为了区分这两种情况，我们把凑不出总体积为j的情况设为-1
第一种情况不选i物品，可以不用判断dp[i-1][j]!=-1,因为我不选i物品，dp[i-1][j]都等于-1，那证明你凑不出来，那dp[i][j]也凑不出来，所以这时候的dp[i][j]=dp[i-1][j];
第二种情况，选i物品，就必须要判断dp[i-1][j-v[i]] :也就是你必须要判断你前面的必须要凑出来j-v[i]的体积，因为你dp[i][j]这个位置选i物品要加体积v[i]的，所以你前面要能凑出来，这时候在加上v[i]的体积就刚刚好
初始化：明确第一行第一列表示啥，第一行我从0个物品中选还是不选凑出体积为0/1/2/3
第一列我选不选0/1/2/3/4物品，凑0体积，那就说明都不选，价值就是0，为了方便，我们只要创建dp表的时候初始化第一行为-1即可
后面的都和第一小问一模一样了
优化 ：
第一种方法：滚动数组的方法，我们可以发现我们的状态转移方程仅仅需要两行的数组
也就是我们在填这一行的数据时，仅仅需要上一行的数据
例如我们在填写第一行数据时，仅仅需要第0行的数据，那我们填第2行时，就可以把第0行滚动下来充当第2行
如果你还觉得两行数组很麻烦，当然也可以用一行数组，
但需要注意你的填表顺序要从右往左
如果你是左往右，你填表的时候需要借助左上角的值，那左往右就是覆盖，填右边的时候就出错
这里运用的原理就是覆盖，你的数组原来是有数据的，也就是上一行的数据，你填这一行时就可以用到这个数据，注意填表从右往左就行（因为你只有一行数组）