算法训练（leetcode）二刷第三十天 | *46. 携带研究材料（第六期模拟笔试）、416. 分割等和子集

*46. 携带研究材料（第六期模拟笔试）

卡码网题目地址

二维数组

01背包问题。用二维数组进行动态规划。

dp[i][j]：访问到第i个物品，在背包容量为j时的最大价值。
初始化：第一个物品在背包容量大于等于其所占空间时的价值为该物品价值。
递推公式：dp[i][j] = max(dp[i-1][j], dp[i][j-cost[i]]+values[i])

其中，

dp[i-1][j]代表上一个物品在容量为j时的最大价值，也就是不把下标为i的物品放入背包；

dp[i][j-cost[i]]+values[i]代表将当前下标为i的物品放入背包，dp[i][j-cost[i]]是获取当背包剩余空间刚好放下当前物品时的最大价值，可以理解为背包腾出当前背包占用空间的大小。

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

// java
import java.util.Scanner;

public class Main{
    
    
    
    public static void main(String[] args){
        int m,n;
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        
        // Bag[] bag = new bag[m];
        
        int[] cost = new int[m];
        for(int i=0; i<m; i++) {
            cost[i] = sc.nextInt();
        }
        
        int[] values = new int[m];
        for(int i=0; i<m; i++) {
            values[i] = sc.nextInt();
        }
        
        int[][] dp = new int [m][n+1];
        
        for(int j=cost[0]; j<=n; j++){
            dp[0][j] = values[0];
        }
        
        for(int i=1; i<m; i++){
            for(int j=0; j<=n; j++){
                if(j<cost[i]) {
                    // 当前容量装不下
                    dp[i][j] = dp[i-1][j];
                }else{
                    // 当前容量能装下
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-cost[i]]+values[i]);
                    
                }
            }
        }
        System.out.println(dp[m-1][n]);
    }
}

滚动数组

这里需要主要在遍历背包容量时是倒序。

因为正序遍历容量会导致一个物品被放入多次：
dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

逆序只放一次：
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

// java
import java.util.Scanner;

public class Main{
    
    
    
    public static void main(String[] args){
        int m,n;
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        
        int[] cost = new int[m];
        for(int i=0; i<m; i++) {
            cost[i] = sc.nextInt();
        }
        
        int[] values = new int[m];
        for(int i=0; i<m; i++) {
            values[i] = sc.nextInt();
        }
        
        
        int[] dp = new int [n+1];
        
        for(int i=0; i<m; i++){
            for(int j=n; j>=cost[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-cost[i]] + values[i]);
            }
        }
        System.out.println(dp[n]);
        
    }
}

416. 分割等和子集

leetcode题目地址

回溯法超时。仍然采用01背包的解题思路。先对数组中的所有元素求和，若元素和无法整除2直接返回false。

dp[j]记录中值为j时的最大的元素和。若dp[j]==j则可以拆分为两个和为j的子集。

使用滚动数组依旧是从后向前遍历。

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

// java
class Solution {
    
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            sum += nums[i];
        }
        if(sum % 2 != 0) return false;
        int mid = sum/2;
        
        
        int[] dp = new int[mid+1];
        for(int i=0; i<nums.length; i++){
            for(int j=mid; j>=nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[mid] == mid;
    }
}