动态规划中01背包问题

动态规划中01背包问题：

这记录一下自己的思考和总结：
详细讲解：添加链接描述

这种题目中有两种解题方法

一是二维数组dp[i][j]表示0-i区间背包容量为j的最大价值

那么可以有两个方向推出来dp[i][j]，

• 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。
• 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

这里我们获取到的值都是从左边和正上方获取值来更新当前值，所以这里可以从左到右来更新背包的容量，因为之前的值都已经好好的存储好了不会在改变

二是一维数组dp[j]表容量为j的背包，所背的物品价值可以最大为dp[j]。

dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包加上物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）

此时dp[j]有两个选择，一个是取自己dp[j] 相当于二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值

递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

这里不能正序可以这么理解:

虽然是一维数组，但是性质和二维背包差不多。我们先来理解倒序遍历，从最后一个元素往前看，看到的都是“上一层的元素”然后每遍历到一个元素，就把当前元素赋值成“当前层”的。这样得到的背包，因为每个元素加上的都是上一层的对应的物品value，所以不会重复。

因为二维数组是根据左上元素来求的，一维数组自然就是靠左边来求的。倒序的时候左边元素再刷新前都是上一层的数据，但正序就不一样了，正序的时候，左边的元素刚刚刷新过，也就是左边的元素已经是本层的了，意味着什么 这样会导致一个物品反复加好几次。