0


Leetcode 刷题笔记(二十四) ——动态规划篇之背包问题:01背包

文章目录

系列文章目录

一、 数组类型解题方法一:二分法
二、数组类型解题方法二:双指针法
三、数组类型解题方法三:滑动窗口
四、数组类型解题方法四:模拟
五、链表篇之链表的基础操作和经典题目
六、哈希表篇之经典题目
七、字符串篇之经典题目
八、字符串篇之 KMP
九、解题方法:双指针
十、栈与队列篇之经典题目
十 一、栈与队列篇之 top-K 问题
十 二、二叉树篇之二叉树的前中后序遍历
十 三、二叉树篇之二叉树的层序遍历及相关题目
十 四、二叉树篇之二叉树的属性相关题目
十 五、 二叉树篇之二叉树的修改与构造
十 六、 二叉树篇之二叉搜索树的属性
十 七、二叉树篇之公共祖先问题
十 八、二叉树篇之二叉搜索树的修改与构造
十 九、回溯算法篇之组合问题
二 十、回溯算法篇之分割、子集、全排列问题
二十一、贪心算法篇之入门题目
二十二、贪心算法篇之进阶题目
二十三、动态规划篇之基础题目
更新中 …


前言

一个商品如果可以重复多次放入是完全背包,而只能放入一次是01背包
刷题路线来自 :代码随想录

题录

01背包问题

LintCode 链接
有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大?
在这里插入图片描述
题解:

/**
     * 状态 F(i,j): 前 i个物品放入大小为 j的背包中所获得的最大价值
     * 递推关系:当前背包放不下新增物品时 A(i-1) < j:
     *              F(i,j) = F(i-1,j)
     *     放得下时: F(i,j) = max{ (F(i-1, j), F(i-1, F(j - A(i-1))) + V(i - 1)}
     *     A(i-1):  新增物品的大小
     *     V(i-1):  新增物品的价格
     *     F(i-1,j): 表示不把第i个物品放入背包中, 所以它的价值就是前i-1个物品放入大小为j的背包的最大价值
     *     F(i-1, j - A[i]) + V[i]:表示把第i个物品放入背包中,价值增加V[i],但是需要腾出j - A[i]的大小放
第i个商品
     *     初始状态:F(i,0) = F(0,j) = 0   第0行和第0列都为0,表示没有装物品时的价值都为0
     *     返回值:F(i,j)
     */publicclassSolution{publicintbackPackII(int m,int[]A,int[]V){int row =A.length;if(row ==0|| m ==0)return0;int[][] dp =newint[row +1][m +1];for(int i =1; i <= row; i++){// 遍历背包for(int j =1; j <= m; j++){// 遍历重量if(A[i -1]> j){// 新增物品质量大于当前背包,放不下
                    dp[i][j]= dp[i -1][j];}else{// 放得下,如果放入新物品要计算出背包剩余大小,看下剩余背包大小最多能装多少然后加上新增物品价格,和不放入新物品背包最大价格对比,取最大。最大价格都在上一层
                    dp[i][j]=Math.max(dp[i -1][j], dp[i -1][j -A[i -1]]+V[i -1]);}}}return dp[row][m];}}

空间优化:一维dp数组(滚动数组)

  1. 寻找最大值时不用去上层 dp 数组中寻找,在原数组上修改,从后向前遍历,因为找背包剩余位置能放下的物品最多价值时需要向前找,且不能放入新物品。
  2. 在遍历的时候在背包空间大于等于新物品的价值就可以,再向前遍历需要进行能不能放下物品的判断,而且也没有意义,放不下的话数组中的值也不会改变。
publicclassSolution{/**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */publicintbackPackII(int m,int[]A,int[]V){int row =A.length;if(m ==0)return0;int[] dp =newint[m +1];for(int i =0; i < row; i++){for(int j = m; j >=A[i]; j--){
                dp[j]=Math.max(dp[j], dp[j -A[i]]+V[i]);}}return dp[m];}}

416. 分割等和子集

Leetcode 链接
在这里插入图片描述
题解:
整个数组和为 sum,找到 sum / 2 的子数组即可
方法一: 回溯(结果超时)
如下两题几乎是一样的,可以用回溯法,解决如下两题
698.划分为k个相等的子集
473.火柴拼正方形

classSolution{boolean flag =false;int sumDfs =0;publicbooleancanPartition(int[] nums){int sum =0;for(int i =0; i < nums.length; i++){
            sum += nums[i];}if(sum %2==1)returnfalse;
        sum = sum /2;dfs(nums, sum,0);return flag;}publicvoiddfs(int[] nums,int sum,int start){if(sumDfs > sum){return;}if(sumDfs == sum){
            flag =true;return;}for(int i = start; i < nums.length; i++){
            sumDfs += nums[i];dfs(nums, sum, i +1);
            sumDfs -= nums[i];}}}

方法二:动态规划(这里直接用 一维dp数组)
背包大小为 sum / 2,物品为数组中的数值,物品的大小和价格都为 num[i]
dp[i] 可以直接看作大小为 i 的背包,装入物品的最大和。
返回值: dp[sum / 2] == sum / 2,sum / 2 大小的背包刚好装入 sum / 2 的物品最大和

classSolution{publicbooleancanPartition(int[] nums){int sum =0;for(int i =0; i < nums.length; i++){
            sum += nums[i];}if(sum %2==1)returnfalse;
        sum = sum /2;int[] dp =newint[sum +1];for(int i =0; i < nums.length; i++){for(int j = sum; j >= nums[i]; j--){
                dp[j]=Math.max(dp[j], dp[j - nums[i]]+ nums[i]);}}return dp[sum]== sum;}}

1049. 最后一块石头的重量 II

Leetcode 链接
在这里插入图片描述
1046. 最后一块石头的重量
将本体的任意石头改成最大的两块石头截然不同的两道题,使用优先级队列解决
题解:
难点:怎么就扯到 dp 了呢?看三叶大神的讲解
评论区大佬一语道破玄机:
因为每一次抵消,实际上都是[a, b, …]变成[a - b, …]或[b-a, …]的过程,最终也必然会得出类似 (b - a) - ( c - d) 这种计算式,展平得 -a + b - c + d = (b+d)-(a+c)这种计算式,b+d >= sum/2 >= a+c,需要做的就是找出a+c不大于sum/2时的最大值,经典背包问题。
dp[v] - (a + c) = b + d、 返回 (b + d) - (a + c)
返回值: sum - dp[v] - dp[v]; 前边的 sum - dp[v] 得到较大部分的和

classSolution{publicintlastStoneWeightII(int[] stones){int sum =0;for(int i : stones){
            sum += i;}int v = sum /2;int[] dp =newint[v +1];for(int i =0; i < stones.length; i++){for(int j = v; j >= stones[i]; j--){
                dp[j]=Math.max(dp[j], dp[j - stones[i]]+ stones[i]);}}// 注意返回值的含义return sum - dp[v]- dp[v];}}

494. 目标和

Leetcode 链接
在这里插入图片描述
题解:
bigSum - smallSum = targetbigSum + smallSum = sum
smallSum = (sum - target) / 2 (因为 smallSum < bigSum) 所以这里选 smallSum,而且由式子都为可知 为非负偶数
多少种运算结果等于 target 的表达式数目由 bigSum - smallSum = target 这里的 bigSum 或 smallSum 的子组合数目决定。故本题相当于求:和为 bigSum 或 smallSum 的子数组最多组合数 可作为01 背包问题。
背包大小由 smallSum 决定,物品大小为 nums[i]。
dp[i][j]: 0 ~ i 个物品放入大小为 j 的背包的最大组合数目

classSolution{publicintfindTargetSumWays(int[] nums,int target){int row = nums.length;int sum =0;for(int i : nums){
            sum += i;}// 和都小于 target 了,返回 0if(sum - target <0)return0;if((sum - target)%2==1)return0;// smallSum 为非负偶数;int smallSum =(sum - target)/2;int[][] dp =newint[row +1][smallSum +1];// 因为刚好放下时,要在不要该物品的最大组合数上加上 1(只放该物品),所以dp[][0] 必须为1,dp[][0]都由 dp[0][0]得来
        dp[0][0]=1;for(int i =1; i <= row; i++){// 第二层背包大小从 0 开始,因为所以dp[][0] 必须为1for(int j =0; j <= smallSum; j++){if(j >= nums[i -1]){// 放得下时,放入前的最大组合数 dp[i - 1][j],加上放入后的最大组合数 = 放入前背包大小 为j - num[i - 1]的最大组合数// num[i - 1]:0 号物品下标从 1 开始, 所以为新增物品下标为 i - 1// j - num[i - 1]:放入后背包还剩的大小
                    dp[i][j]= dp[i -1][j]+ dp[i -1][j - nums[i -1]];}else{// 放不下时
                    dp[i][j]= dp[i -1][j];}}}return dp[row][smallSum];}}

空间优化(一维滚动 dp 数组):

classSolution{publicintfindTargetSumWays(int[] nums,int target){int row = nums.length;int sum =0;for(int i : nums){
            sum += i;}if(sum - target <0)return0;if((sum - target)%2==1)return0;int smallSum =(sum - target)/2;int[] dp =newint[smallSum +1];
        dp[0]=1;for(int i =0; i < row; i++){for(int j = smallSum; j >= nums[i]; j--){
                dp[j]= dp[j]+ dp[j - nums[i]];}}return dp[smallSum];}}

474. 一和零 (滚动二维dp)

Leetcode 链接
在这里插入图片描述
总结

  1. 最大和类型的递推公式 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);降维后:dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
  2. 求组合类型的递推公式 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];降维后:dp[j] = dp[j] + dp[j - nums[i]];

本文转载自: https://blog.csdn.net/a1241692733/article/details/123141594
版权归原作者 a1241692733 所有, 如有侵权,请联系我们删除。

“Leetcode 刷题笔记(二十四) &mdash;&mdash;动态规划篇之背包问题:01背包”的评论:

还没有评论