day36+day37 0-1背包

### 9.9 01背包问题（一维+二维）
背包问题分类：01背包（一种物品只有一个），完全背包（一种物品有无数个），多重背包（不同物品有不同数量）

46. 携带研究材料（第六期模拟笔试）
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。 
小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
输入描述
第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。
第二行包含 M 个正整数，代表每种研究材料的所占空间。 
第三行包含 M 个正整数，代表每种研究材料的价值。
输出描述
输出一个整数，代表小明能够携带的研究材料的最大价值。

暴力解法：每个物品只有取和不取，用回溯算法枚举就可以。时间复杂度n2

 01背包问题 二维 
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  
https://www.bilibili.com/video/BV1cg411g7Y6  
`dp[i][j]:i 来表示物品、j表示背包容量
`dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
如：`dp[1][4] 表示什么意思呢?
任取物品0、物品1放入容量为4的背包中，最大价值是`dp[1][4]。

二维数组遍历顺序：先遍历物品，再遍历背包/先遍历背包，再遍历物品都可以。因为需要的值就是正上方和左上角的值。

遇到的问题：
非leetcode包装好的方法，需要获取数据
写的时候也有一些细节需要注意：
```java
import java.util.Scanner;  
  
public class bag01TwoDimensional {  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        int num = sc.nextInt();  
        int bagCapacity = sc.nextInt();  
  
        int[] materialSpace = new int[num];  
        int[] materialValue = new int[num];  
  
        for (int i = 0; i < num; i++) {  
            materialSpace[i] = sc.nextInt();  
        }  
        for (int i = 0; i < num; i++) {  
            materialValue[i] = sc.nextInt();  
        }  
  
        //dp初始化  
        int[][] dp = new int[num][bagCapacity+1];  
        //初始化第一行：有简洁的写法，即直接从materialSpace[0]开始遍历。如果它大于包的容量，则不进入循环。  
        for (int i = materialSpace[0]; i <= bagCapacity; i++) {  
            dp[0][i] = materialValue[0];  
        }  
        //初始化第一列：其实不用写，默认的初始值就是0  
  
        for (int i = 1; i < num; i++) {  
            for (int j = 0; j <= bagCapacity; j++) {  
//                //不要第i个物品  
//                int noI = dp[i-1][j];  
//                //要第i个物品  
//                int withI = dp[i-1][j-materialSpace[i]] + materialValue[i];  
                if(materialSpace[i] > j){  
                    dp[i][j] = dp[i-1][j];  
                }else{  
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-materialSpace[i]] + materialValue[i]);  
                }  
            }  
        }  
//        for (int i = 0; i < num; i++) {  
//            for (int j = 0; j <= bagCapacity; j++) {  
//                System.out.print("dp["+i+"]["+j+"] = "+ dp[i][j]+"  ");  
//            }  
//            System.out.println();  
//        }  
        System.out.println(dp[num-1][bagCapacity]);  
    }  
}
```

 01背包问题 一维 
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-2.html  

https://www.bilibili.com/video/BV1BU4y177kY  

把矩阵压缩成一行，把上一层拷贝到下一层。滚动数组。
1.确定dp数组（dp table）以及下标的含义
dp`[j] ：容量为j的背包能装进物品的最大价值。

2.确定递推公式 
不放物品i：dp`[j]
放物品i：dp`[j-weight[i]]+value[i]

3.dp数组如何初始化（0/1确认很有讲究，很重要）
dp`[0] = 0;

4.确定遍历顺序
倒序遍历。如果正序遍历，会导致前面的物品被反复加入

5.打印dp数组（动态规划代码简短，直接看打印出来的dp数组是不是和自己设想的一致）
```java
public class bag02OneDimensional {  
    public static void main(String[] args) {  
//        int materialNum = 6;  
//        int capacity = 6;  
//  
//        int[] weight = {2,2,3,1,5,2};  
//        int[] value = {2,3,1,5,4,3};  
  
        //get data  
        Scanner sc = new Scanner(System.in);  
        int materialNum = sc.nextInt();  
        int capacity = sc.nextInt();  
  
        int[] weight = new int[materialNum];  
        int[] value = new int[materialNum];  
  
        for (int i = 0; i < materialNum; i++) {  
            weight[i] = sc.nextInt();  
        }  
  
        for (int i = 0; i < materialNum; i++) {  
            value[i] = sc.nextInt();  
        }  
  
        int[] dp = new int[capacity+1];//当背包容量为i时，包内物品的最大价值为dp[i]  
  
        for (int i = 0; i < materialNum; i++) {  
            for (int j = capacity; j >= weight[i]; j--) {  
                int withoutI = dp[j];  
                int withI = dp[j-weight[i]] + value[i];  
                dp[j] = Math.max(withoutI,withI);  
                //System.out.println("dp["+i+"]["+j+"]"+" = " + dp[j]);  
            }  
        }  
  
        System.out.println(dp[capacity]);  
  
    }  
}
```

### 9.10 416. Partition Equal Subset Sum
Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
https://leetcode.cn/problems/partition-equal-subset-sum/description/
 416. 分割等和子集  
本题是 01背包的应用类题目
https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html    
https://www.bilibili.com/video/BV1rt4y1N7jE

01背包，里面的元素能不能刚好装满容量为数组元素和二分之一的背包。
物品的重量和价值相同

动态规划五部曲：
1.确定dp数组（dp table）以及下标的含义
dp`[j]:背包总容量为j，放进物品后，背的最大重量为dp[j]。

2.确定递推公式 

3.dp数组如何初始化（0/1确认很有讲究，很重要）
4.确定遍历顺序
后序遍历

5.打印dp数组（动态规划代码简短，直接看打印出来的dp数组是不是和自己设想的一致）

自己做的时候错误点：
没有剪枝。当总和为奇数时，直接返回false即可。
```java
public class partitionEqualSubsetSum {  
    public boolean canPartition(int[] nums) {  
        int sum = 0;  
        for (int i = 0; i < nums.length; i++) {  
            sum  += nums[i];  
        }  
        if(sum%2 == 1) return false;  
        int target = sum/2;  
  
        int[] dp = new int[target + 1];  
        //先遍历物品，后遍历背包  
        for (int i = 0; i < nums.length; i++) {  
            for (int j = target; j >= nums[i]; j--) {  
//                int withI = dp[j - nums[i]] + nums[i];  
//                int withoutI = dp[j];  
                dp[j] = Math.max(dp[j - nums[i]] + nums[i],dp[j]);  
            }  
        }  
        return dp[target] == target;  
    }  
}  
class partitionEqualSubsetSumTest{  
    public static void main(String[] args) {  
        int[] nums = {1,2,3,5};  
        partitionEqualSubsetSum example = new partitionEqualSubsetSum();  
        System.out.println(example.canPartition(nums));  
  
    }  
}
```

### 9.11 1049. Last Stone Weight II
You are given an array of integers stones where stones`[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
https://leetcode.cn/problems/last-stone-weight-ii/description/
1049. 最后一块石头的重量 II
本题就和 昨天的 416. 分割等和子集 很像了，可以尝试先自己思考做一做。 
https://www.bilibili.com/video/BV14M411C7oV 
https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html  

把石头尽量分成重量相近的两堆，比如总重量为23的石头堆分成11和12。

```java
public class lastStoneWeight2 {  
    public int lastStoneWeightII(int[] stones) {  
        int sum = 0;  
        for (int i = 0; i < stones.length; i++) {  
            sum += stones[i];  
        }  
        int target = sum/2;  
  
        int[] dp = new int[target+1];  
  
        for (int i = 0; i < stones.length; i++) {  
            //如果此时背包剩余容量小于待加入石头的重量，则没必要进入循环  
            //If the remaining capacity of the backpack at this time is less than the weight of the stones to be added, there is no need to enter the loop  
            for (int j = target; j >= stones[i]; j--) {  
                dp[j] = Math.max(dp[j],dp[j-stones[i]] + stones[i]);  
            }  
        }  
  
        //return Math.abs(dp[target]-(sum-dp[target]));  
        return sum - 2*dp[target];  
    }  
}  
class lastStoneWeight2Test{  
    public static void main(String[] args) {  
        lastStoneWeight2 example = new lastStoneWeight2();  
        int[] nums = {31,26,33,21,40};  
        System.out.println(example.lastStoneWeightII(nums));  
    }  
}
```

### 9.12 494. Target Sum
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
For example, if `nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.
https://leetcode.cn/problems/target-sum/description/
 494. 目标和 
大家重点理解 递推公式：`dp[j] += dp[j - nums[i]]，这个公式后面的提问 我们还会用到。  
https://www.bilibili.com/video/BV1o8411j73x
https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html  

分成两个子集，加法在一个子集(left)，减法在一个子集(right)。

sum = left + right   ===>   left = sum - right
target = left - right ===>   left = target + right
===> 2left = sum + target
left = (sum+target)/2
如果不能整除，就是凑不成target，直接返回0
有多少种情况可以装满背包，就返回多少
nums = `[1,1,1,1,1], target = 3

dp`[j] : 装满容量为j的背包有dp[j] 种方法

背包里已有：
物品1:  有dp`[4] 种方法凑成dp[5];
物品2:  有dp`[3] 种方法凑成dp[5];

递推公式： `dp[j] += dp[j-num[i]];

初始化：`dp[0] = 1;

```java
public class targetSum {  
    public int findTargetSumWays(int[] nums, int target) {  
        int sum = 0;  
        for (int i : nums) {  
            sum += i;  
        }  
        //如果target的绝对值大于sum，那么无解  
        if ((sum + target) % 2 == 1 || Math.abs(target) > sum) return 0;  
  
        int capacity = (sum + target) >> 1;  
  
        int[] dp = new int[capacity + 1];  
        dp[0] = 1;  
        for (int i = 0; i < nums.length; i++) {  
            for (int j = capacity; j >= nums[i]; j--) {  
                dp[j] += dp[j-nums[i]];  
            }  
        }   
        return dp[capacity];  
    }  
}  
  
class targetSumTest {  
    public static void main(String[] args) {  
        targetSum example = new targetSum();  
        int[] nums = {1,1,1,1,1};  
        int target = 3;  
        System.out.println(example.findTargetSumWays(nums, target));  
    }  
}
```

### 9.13 474. Ones and Zeroes
You are given an array of binary strings strs and two integers m and n.
Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset.
A set x is a subset of a set y if all elements of x are also elements of y.
https://leetcode.cn/problems/ones-and-zeroes/description/

 474.一和零  
通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。
https://www.bilibili.com/video/BV1rW4y1x7ZQ 
https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html  

装满容器最多多少个物品？
m个0 n个1 凑成子集
背包：最多有m个0，n个1。装满这个背包最多有多少个物品？
dp`[i][j] 装满i个0，j个1的背包最多有dp[i][j]个物品

待加入物品有x个0，y个1
dp`[i][j] = Math.max((dp[i-x][j-y] + 1),dp[i][j])

初始化：
dp`[0][0] = 0;
非零坐标也初始化为0。防止递推公式求出的值被初始值覆盖。

```java
public class onesAndZero {  
    public int findMaxForm(String[] strs, int m, int n) {  
        int[][] dp = new int[m + 1][n + 1];  
  
        //iterate items first  
        for (String s : strs) {  
            int x = 0;  
            int y = 0;  
            //to get how many 0 and i in this element  
            char[] chars = s.toCharArray();  
            for (char c : chars) {  
                if (c == '0') {  
                    x++;  
                } else {  
                    y++;  
                }  
            }  
  
            //and then iterate the bag  
            for (int i = m; i >= x; i--) {  
                for (int j = n; j >= y; j--) {  
                    dp[i][j] = Math.max((dp[i - x][j - y] + 1), dp[i][j]);  
                }  
            }  
        }  
        return dp[m][n];  
    }  
}  
  
class onesAndZeroTest {  
    public static void main(String[] args) {  
        onesAndZero example = new onesAndZero();  
        String[] strs = {"10","0","1"};  
        int m = 1;  
        int n = 1;  
  
        System.out.println(example.findMaxForm(strs,m,n));  
  
    }  
}
```