当前位置:   article > 正文

【力扣动态规01背包问题】:416. 分割等和子集 1049. 最后一块石头的重量 II_力扣01背包

力扣01背包

dda本文基于公众号"代码随想录",总结而来:https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html#_01-%E8%83%8C%E5%8C%85

dsada关于动态规划的背包问题,我们重点掌握01背包和完全背包就够用了(完全背包又是也是01背包稍作变化而来,即:完全背包的物品数量是无限的。)。

01 背包

dda有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次,求解将哪些物品装入背包里物品价值总和最大。
dsdsd在这里插入图片描述
dda这是标准的背包问题,以至于很多同学看了这个自然就会想到背包,甚至都不知道暴力的解法应该怎么解了。这样其实是没有从底向上去思考,而是习惯性想到了背包,那么暴力的解法应该是怎么样的呢?每一件物品其实只有两个状态,取或者不取,所以可以使用回溯法搜索出所有的情况,那么时间复杂度就是O(2^n),这里的n表示物品数量。

dda[注]:暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化!

01 背包示例讲解

dda背包最大重量为4。物品如下,问背包能背的物品最大价值是多少?
ddasdsssssssssssssssssssssadassadasdda在这里插入图片描述
ddasss在这里插入图片描述
dda完整代码:

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagSize = 4;
        testWeightBagProblem(weight, value, bagSize);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
        int wLen = weight.length, value0 = 0;
        //定义dp数组:dp[i][j]表示背包容量为j时,前i个物品能获得的最大价值
        int[][] dp = new int[wLen + 1][bagSize + 1];
        //初始化:背包容量为0时,能获得的价值都为0(也可以不写,毕竟都是0)
        for (int i = 0; i <= wLen; i++){
            dp[i][0] = value0;
        }
        //遍历顺序:先遍历物品,再遍历背包容量
        for (int i = 1; i <= wLen; i++){
            for (int j = 1; j <= bagSize; j++){
                if (j < weight[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //输出
        for (int i = 0; i <= wLen; i++){
            for (int j = 0; j <= bagSize; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
=======================================================================================
结果:
		0 0 0 0 0 
		0 15 15 15 15 
		0 15 15 20 35 
		0 15 15 20 35 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39

01 背包示例讲解—一维dp数组(滚动数组)

dda背包最大重量为4。物品如下,问背包能背的物品最大价值是多少?
ddasss在这里插入图片描述
dda完整代码:

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组:dp[j]表示背包容量为j时,能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序:先遍历物品,再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

01 背包----416. 分割等和子集

ddsda在这里插入图片描述
ddsda在这里插入图片描述

/*
* 一维数组
*/
class Solution {
    public boolean canPartition(int[] nums) {
        if(nums==null || nums.length == 0)  
            return false;
        int sum =0;
        for(int num: nums){
            sum+=num;
        }
        if((sum & 1) == 1)
            return false;
        int target  =  sum/2;

        //dp: dp[i]表示 背包总容量是i,最大可以凑成i的子集总和为dp[i]。
        int[] dp = new int[target+1]; 

        for(int i=0 ; i<nums.length ; i++){
            for(int j=target ; j>=nums[i] ; j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[target] == target;
    }
}
=========================================================================================================
/*
二维数组:
*/
class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if((sum & 1) == 1){
            return false;
        }
        int target = sum / 2;   

        //也就是说求含有target即可,通过动态规划来做
        boolean[][] dp = new boolean[len][target+1];
        //dp[i][j]表示从[0,i]这个子区间中能挑选一些正整数,每个数只能用一次,使得这些数的和恰好等于j
        //先填第0行,第一个数只能让容积为它自己的背包恰好装满(也就是边界)
        if(nums[0] <= target){
            dp[0][nums[0]] = true;
        }
        /*再想转移方程
            不选择nums[i],[0,i-1]这个子区间已经有一部分元素,使得它们的和为j,dp[i][j] =true
            选择nums[i],[0,i-1]这个子区间内的到一部分元素,使得它们的和为j-nums[i] 
        再填后面几行
        */
        for(int i=1 ; i<len ; i++){
            for(int j=1 ; j<=target ; j++){
                //先把上一行抄下来再修正
                dp[i][j] = dp[i-1][j];
                if(nums[i] == j){
                    dp[i][j] = true;
                    continue;
                }
                if(nums[i] < j){
                    dp[i][j] = dp[i-1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[len-1][target];
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

01 背包----1049. 最后一块石头的重量 II

在这里插入图片描述
ddsda在这里插入图片描述

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int weight : stones){
            sum+=weight;
        }
        int target = sum/2;
        int[] dp = new int[target+1];
        for(int i=0 ; i<stones.length ; i++){
            for(int j=target ; j>=stones[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-dp[target] - dp[target];
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/840318
推荐阅读
相关标签
  

闽ICP备14008679号