代码随想录算法训练营第三十四天-01背包问题 二维、01背包问题 一维、416分割等和子集

• 前言
  状态：前两题为背包基础题，直接看的题解。416 也是看的解析。

• 更新

24-06-20 初始记录

初步题解

416 分割等和子集

题目链接：(https://leetcode.cn/problems/partition-equal-subset-sum)

看解析

01 背包问题 二维

题目链接 + 解析：(https://programmercarl.com/背包理论基础01背包-1.html)

1. 确定 dp[i][j] 的含义：从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

2. 递推公式：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])（即，不存放当前物品/存放当前物品）

3. dp 数组的初始化：dp[i][0] 均为 0，dp[0][j] 需要根据实际情况来。

4. 遍历顺序：从前向后遍历。

5. 打印 dp 数组（用于 debug）

public static void main(String[] args) {  
    integerBreak(4, new int[][]{{1, 15}, {3, 20}, {4, 30}});  
}  
  
/**  
 * 二维数组解法  
 * @param n 背包大小  
 * @param item 物品及重量及价值  
 */
public static void integerBreak(int n, int[][] item) {  
    int[][] dp = new int[item.length][n + 1];  
  
    for (int i = 1; i < dp[0].length && n >= item[0][0]; i++) {  
        dp[0][i] = item[0][1];  
    }  
  
    for (int i = 1; i < item.length; i++) {  
        for (int j = 1; j <= n; j++) {  
            if (j - item[i][0] < 0) {  
                dp[i][j] = dp[i - 1][j];  
            }else {  
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - item[i][0]] + item[i][1]);  
            }  
        }  
    }  
  
    System.out.println(Arrays.deepToString(dp));  
}

01 背包问题 一维

题目链接 + 解析：(https://programmercarl.com/背包理论基础01背包-2)

1. 确定 dp[j] 的含义：从物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

2. 递推公式：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])（即，要么等于原值，要么等于放入物品的值）

3. dp 数组的初始化：dp[0] = 0。

4. 遍历顺序：从后向前遍历。（这里需要注意，因为递推公式内需要上一层的原值，只有倒序遍历，可以获取上一层的原值。）

5. 打印 dp 数组（用于 debug）

/**  
 * 一维数组解法  
 * @param n 背包大小  
 * @param item 物品及重量及价值  
 */  
public void integerBreak1(int n, int[][] item) {  
    int[] dp = new int[n + 1];  
  
    for (int[] ints : item) {  
        for (int j = dp.length - 1; j >= ints[0]; j--) {    
            dp[j] = Math.max(dp[j], dp[j - ints[0]] + ints[1]);  
        }  
    }  
  
    System.out.println(Arrays.toString(dp));  
}

416 分割等和子集

解析：(https://programmercarl.com/0416.分割等和子集.html)

1. 确定 dp[j] 的含义：从物品里任意取，求总量的最大值，判断是否等于 j 即 sum/2。这题要抽象，设置 i 位置的重量和价值都为 i

2. 递推公式：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])（如果 dp[j] == j 说明，集合中的子集总和正好可以凑成总和 j）

3. dp 数组的初始化：因为是正整数数组，所以可以初始化为 0。

4. 遍历顺序：从后向前遍历。

5. 打印 dp 数组（用于 debug）

public boolean canPartition(int[] nums) {  
    int sum = Arrays.stream(nums).sum();  
    if (sum % 2 != 0) {  
        return false;  
    }  
  
    int[] dp = new int[sum / 2 + 1];  
  
    for (int num : nums) {  
        for (int j = dp.length - 1; j >= num; j--) {    
            dp[j] = Math.max(dp[j], dp[j - num] + num);  
        }  
        if (dp[sum / 2] == sum / 2) {  
            return true;  
        }  
    }  
    return false;  
}