LeetCode Day30 Dynamic Programming Part 3

0-1 Bag Problem

Description of the topic

Ming is a scientist who needs to attend an important international scientific conference to present his latest research. He needs to bring some research materials with him, but he has limited space in his suitcase. These research materials include experimental equipment, literature, experimental samples, etc., each of which occupies a different space and has a different value.

Ming's luggage space is N. Ask Ming how he should choose to carry the research materials with the greatest value. Each research material can only be chosen once, and there are only two choices: choose or don't choose, and no cutting can be done.

Input Description
The first line contains two positive integers, the first integer M represents the type of research materials, and the second positive integer N represents Ming's luggage space.

The second line contains M positive integers representing the space occupied by each type of research material.

The third row contains M positive integers representing the value of each research material.

Output Description
Output an integer representing the maximum value of research materials that Ming can carry.

Input Example
6 1
2 2 3 1 5 2
2 3 1 5 4 3

Output example
5

Hints
Ming is able to carry 6 research materials, but the luggage space is only 1, and the research material that occupies 1 space is worth 5, so the final answer is output 5.

Data range:
1 <= N <= 5000
1 <= M <= 5000
The space occupied by the research materials and the value of the research materials are both less than or equal to 1000.

public class Main{
    public static void main (String[] args) {
    /* code */
    Scanner s = new Scanner(System.in);

        int M = s.nextInt();
        int N = s.nextInt();
        // clear buffer symbol /n
        s.nextLine();

    String w = s.nextLine();
    String v = s.nextLine();

    int[] weight = Arrays.stream(w.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();
    int[] value = Arrays.stream(v.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();

    int[][] dp = new int[M][N+1];


    for(int i=weight[0]; i<=N; i++){
        dp[0][i] = value[0];
    }

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

        }
    }

    System.out.println(dp[M-1][N]);
    }
}

1, the dp array means that we can obtain the maximum value for item i and target bag size j. The row indicates the item, and the column represents the size of the bag.

2, for init, we init the 1st row and 1st col( but actually we init the col by default 0, that mean )

3, the regression relation is that: for each item:
a, if the weight of the item is heavier than the bag's size, we cannot choose the item and the current size is the size of the collection of the previously chosen items.
b, if the weight of the item is ok, we have to compare the size of the collection of the previously chosen items minus the size of the current item (if we do not do it, the total size will be the size + the size of the current item, it will break the logic of our dp array).

Here, is the order of the double loop, because we can use a 2-D array to record all results and search for the current row from the previous row.

Also, we can use a 1-D array to realize it.

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

change to

        int[] dp = new int[target+1];

        for(int i=1; i<nums.length; i++){
            for(int j=target; j>=1; j--){
                if(nums[i] > j){
                    continue;
                }
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);    
            }
        }

---

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.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100
Original Page

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum%2==1){
            return false;
        }
        int target = sum>>1;
        int[][] dp = new int[nums.length][target+1];

        for(int i=nums[0]; i<=target; i++){
            dp[0][i] = nums[0];
        }

        for(int i=1; i<nums.length; i++){
            for(int j=1; j<=target; j++){
                if(nums[i] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
                }     
            }
        }

        return dp[nums.length-1][target] == target;  
    }