淮南网站开发,网站公司建立,英文网站 icp备案号,企业公司网站制作文章目录 day41学习内容一、 01背包之二维数组解法1.1、什么是01背包1.2、动态规划五部曲1.2.1、 确定dp数组#xff08;dp table#xff09;以及下标的含义1.2.2、确定递推公式1.2.3、 dp数组如何初始化1.2.4、确定遍历顺序1.2.5、计算并返回最终结果 二、 01背包之一维数组… 文章目录 day41学习内容一、 01背包之二维数组解法1.1、什么是01背包1.2、动态规划五部曲1.2.1、 确定dp数组dp table以及下标的含义1.2.2、确定递推公式1.2.3、 dp数组如何初始化1.2.4、确定遍历顺序1.2.5、计算并返回最终结果 二、 01背包之一维数组解法2.1、动态规划五部曲2.1.1、 确定dp数组dp table以及下标的含义2.1.2、确定递推公式2.1.3、 dp数组如何初始化2.1.4、确定遍历顺序二维动态规划从二维到一维的转化为什么要逆序更新具体示例 三、 分割等和子集3.1、动态规划五部曲3.1.1、 确定dp数组dp table以及下标的含义3.1.2、确定递推公式3.1.3、 dp数组如何初始化3.1.4、确定遍历顺序3.1.5、计算并返回最终结果 1.3、代码 总结1.感想2.思维导图 day41学习内容 day41主要内容 01背包之二维数组解法01背包之一维数组解法分割等和子集 声明 本文思路和文字引用自《代码随想录》
一、 01背包之二维数组解法
1.1、什么是01背包
1.2、动态规划五部曲
1.2.1、 确定dp数组dp table以及下标的含义
- 考虑前i个物品当背包容量为j时的最大价值。或者说
- 从物品0到i之间任意取一个物品放到重量为j的背包中的最大价值1.2.2、确定递推公式
在0-1背包问题中dp[i][j]通常表示在考虑前i个物品且背包容量为j时能够获得的最大价值。当我们在处理第i个物品时面临的选择是放入这个物品或者不放入这个物品。
在0-1背包问题中递推公式通常写为
dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])其中
dp[i][j]考虑前i个物品当背包容量为j时的最大价值。dp[i-1][j]不放入第i个物品时考虑前i-1个物品背包容量为j的最大价值。 如果选择不放入第i个物品那么背包中的物品组合应该与考虑前i-1个物品时背包容量为j的情况相同。因为我们没有使用额外的容量来放置第i个物品所以背包的容量和内容保持不变相当于在做决策时忽略了第i个物品。因此此时的公式为dp[i-1][j]表示的是在不选择第i个物品的情况下考虑前i-1个物品时能够获得的最大价值。这反映了一个关键的动态规划概念即利用子问题的解来构建更大问题的解。 dp[i-1][j-w[i]] v[i]放入第i个物品时的情况这里w[i]是第i个物品的重量v[i]是第i个物品的价值。这表示如果放入第i个物品那么背包剩余容量为j-w[i]对应的最大价值应加上第i个物品的价值v[i]。
1.2.3、 dp数组如何初始化
在01背包问题中dp[i][j]表示在前i个物品中选择一些物品使得这些物品的总重量不超过j时这些物品的最大总价值。因此dp[0][j]表示当没有物品可以选择时任何容量j的背包的最大价值都是0因为我们什么也装不进去。同样地dp[i][0]表示当背包的容量为0时不论有多少物品可供选择我们都无法装入任何物品所以最大总价值为0。
1.2.4、确定遍历顺序
从前向后遍历没啥好说的
1.2.5、计算并返回最终结果
无 二、 01背包之一维数组解法
2.1、动态规划五部曲
2.1.1、 确定dp数组dp table以及下标的含义
- dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。2.1.2、确定递推公式
直接给结论
dp[j] max(dp[j], dp[j - weight[i]] value[i]);2.1.3、 dp数组如何初始化
dp[0] [0]
2.1.4、确定遍历顺序
需要逆序遍历。
二维动态规划
假设我们有两个物品其中
物品1的重量为w[1] 2价值为v[1] 3物品2的重量为w[2] 3价值为v[2] 4背包的总容量为W 5。
我们使用二维数组dp[i][j]来表示考虑到第i个物品时背包容量为j的最大价值。
初始化dp[0][j] 0因为没有物品时价值为0。对于每个物品i我们遍历所有可能的背包容量j更新dp[i][j]。
从二维到一维的转化
关键点在于观察到更新dp[i][j]时只需要前一行的信息即dp[i-1][...]。因此如果我们能确保在更新dp[j]时dp[j-w[i]]总是代表加入当前物品前的状态那么我们就可以只用一维数组来保存所有需要的信息。
为什么要逆序更新
假设我们正向更新即j从小到大更新。当我们更新dp[j]时dp[j-w[i]]可能已经被当前物品的加入更新过了这意味着我们可能会错误地将同一个物品加入背包多次。
逆序更新即j从大到小更新确保在更新dp[j]时dp[j-w[i]]还没有被当前物品的加入影响因为我们还没有到达更小的j值。这样每个物品只会被考虑加入一次。
具体示例
让我们以背包总容量W 5为例来具体分析这个过程。假设我们现在处理物品1重量2价值3。 在二维动态规划中我们可能得到类似dp[1][j]的更新其中j从1到5。 转换为一维后我们同样需要更新dp[j]但是逆序处理。
对于物品1初始dp为[0, 0, 0, 0, 0, 0]考虑容量从0到5。 正向考虑如果我们先更新dp[2]为3加入物品1当我们到达dp[4]时可能错误地再次考虑加入物品1因为它看到的dp[2]已经反映了物品1的加入。 逆序更新我们从dp[5]开始往回看。当更新dp[5]时dp[3]对应j-w[i]还未被更新确保我们正确地只考虑加入物品1一次。
三、 分割等和子集
416.原题链接
3.1、动态规划五部曲
3.1.1、 确定dp数组dp table以及下标的含义
- dp[j]表示 背包总容量所能装的总重量是j放进物品后背的最大重量为dp[j]。3.1.2、确定递推公式
dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);3.1.3、 dp数组如何初始化
dp[0] 0java中新建数组会自动赋值所有的元素的值都为0
3.1.4、确定遍历顺序
逆序遍历
3.1.5、计算并返回最终结果
return dp[target] target;
1.3、代码
class Solution {public boolean canPartition(int[] nums) {if(nums null || nums.length 0) return false;int n nums.length;int sum 0;for(int num : nums) {sum num;}//总和为奇数不能平分if(sum % 2 ! 0) return false;int target sum / 2;//开始背包逻辑int[] dp new int[target 1];for(int i 0; i n; i) {for(int j target; j nums[i]; j--) {// 此时价值为nums[i]重量也为nums[i]dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}}return dp[target] target;}
}总结
1.感想
好难好难。。。
2.思维导图 本文思路引用自代码随想录感谢代码随想录作者。
