【力扣动态规01背包问题】：416. 分割等和子集 1049. 最后一块石头的重量 II_力扣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