01背包问题滚动数组(一维数组)

看了好几天的背包问题。。。终于有了一点浅显的理解
一开始学完01背包的二维写法，再看一维写法是一脸懵逼的，自己推导了几遍过程，终于是理解了！！！分享一下蒟蒻的心得

问题如下：有n个重量和价值分别为wi,vi的物品。从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
输入：n=4 (w,v)={(2,3),(1,2),(3,4),(2,2)}
输出：7
最大负重为5

如果学过01背包的二维数组写法，那么应该会发现若是递推顺序是正序，那么我们需要用到的是左上方和正上方的数据，如下图

核心代码如下：

for (int i = 0; i < 4; i++) {
		for (int j = bag_w; j >=w[i]; j--) 
				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

 
 

 
 
1
2
3

bag_w为重量上限

推导过程如下：
dp[]右边是一维数组下标

比如说数塔问题，就是一行一行地去更新，也就是在一维数组里面不断滚动

可以试着去推导，如果是正序的话，同一个物品可能会多次使用，
例如，i=0时，dp[2]=3,dp[3]=3,dp[4]=6,注意了，这里dp[4]=max(dp[4],dp[4-w[0]+v[0])=6;可以看到，在dp[2]的基础上，又放入了物品1，这就变成了完全背包而不是01背包了。

切记，一维必须是逆序的，而二维可以正序也可以逆序。