代码随想录算法训练营第三十五天 | 46. 携带研究材料、416. 分割等和子集

46. 携带研究材料

题目链接：https://kamacoder.com/problempage.php?pid=1046
文档讲解：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
状态：已完成

思路（二维数组）：$dp[i][j]$表示使用前i个物品，在空间大小为j的背包中，所能取得的最大价值

• $dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])$，根据是否选择第i个物品划分状态
• 初始化：$dp[0][i]=dp[i][0]=0$，即物品数量为0，或背包空间为0，得到的价值为0

时间复杂度：$O(M\ast N)$；空间复杂度：$O(M\ast N)$

import java.util.Scanner;

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

        System.out.println(dp[m][n]);
        
    }
}

优化思路（一维数组）：$dp[i]$表示背包空间为i时的最大价值

• $dp[i]=max(dp[i],dp[i-weight[j]]+val[j])$
• 遍历顺序：外层循环是物品，内层循环为背包空间
• 为了确保计算$dp[i]$时，$dp[i-weight[j]]$未被覆盖，内层循环需要倒着遍历

时间复杂度：$O(M\ast N)$；空间复杂度：$O(N)$

import java.util.Scanner;

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

        System.out.println(dp[n]);
    }
}

416. 分割等和子集

题目链接：https://leetcode.cn/problems/partition-equal-subset-sum/description/
文档讲解：https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
状态：需二刷，第一时间想到的思路是回溯，无法把题目抽象为背包问题

思路1（回溯，超时）：将问题转换为在数组中寻找一个子集，和为sum/2

• 遍历数组，针对每个元素，有选与不选两个可能，通过回溯找到可能的解

时间复杂度：$O(2^N)$，所有可能的组合数；空间复杂度：$O(N)$，递归层数

// 如果总和为奇数，直接返回false
// 问题转换为：寻找一个子集，和为sum/2
// 解法：回溯

class Solution {
    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;
        return backtrack(0, nums, 0, target);
    }

    public boolean backtrack(int idx, int[] nums, int tmpSum, int target){
        if(tmpSum == target)
            return true;
        if(tmpSum > target || idx == nums.length)
            return false;
        
        // 1.不选nums[idx]
        if(backtrack(idx+1, nums, tmpSum, target))
            return true;
        return backtrack(idx+1, nums, tmpSum+nums[idx], target);
    }
}

思路2（背包DP）：回溯做法中每个元素有选与不选两种可能，可以类比于背包问题，因此使用动态规划求解

• 背包容量m是总和的一半，物品就是数组中的元素，重量和价值为元素大小
• 最终通过比较$dp[n+1][m+1]$与m是否相等，即可确认是否存在和为m的子集

时间复杂度：$O(N\ast M)$；空间复杂度：$O(N\ast M)$

// 背包容量：sum / 2
// 物品：元素
// dp[i,j]：只考虑前i个元素的最大价值
// 对比dp[n, sum/2]和sum/2，如果相等就返回true

class Solution {
    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 n = nums.length;
        int[][] dp = new int[n+1][target+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=target;j++){
                int tmpVal = j >= nums[i-1] ? dp[i-1][j-nums[i-1]]+nums[i-1] : 0;
                dp[i][j] = Math.max(dp[i-1][j], tmpVal);
            }
        }

        return dp[n][target] == target;
    }
}