背包问题

linwt · linwt · commit 46d23fb8b581 · 2022-03-13T22:37:56.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -58,6 +58,7 @@
 322. 零钱兑换
 338. 比特位计数
 406. 根据身高重建队列
+416. 分割等和子集
 437. 路径总和
 448. 找到所有数组中消失的数字
 461. 汉明距离
diff --git a/leetcode_Java/Solution0322.java b/leetcode_Java/Solution0322.java
@@ -41,15 +41,15 @@ private int dfs(int[] memo, int[] coins, int amount) {
 
 
 /*
-动态规划
+动态规划：完全背包，先物品再背包是计算组合，先背包再物品是计算排列，本题物品背包顺序无关，必须正序遍历背包才能重复使用物品
 1、题目：给你一个整数数组coins，表示不同面额的硬币；以及一个整数amount，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。你可以认为每种硬币的数量是无限的。
 2、题目简化：求凑成总金额amount所需的最少硬币数
 3、定义dp数组：dp[i] 表示凑成总金额i所需的最少硬币数
 4、状态转移方程：dp[i] = Math.min(dp[i], dp[i-coin]+1); 需要比较多种硬币情况下的最小值
 5、初始化：
    dp[i]=amount+1; 填充一个不可能的硬币数，使得不影响计算，也方便状态转移时取最小值
    dp[0]=0; 表示凑成总金额0所需的最少硬币数为0，方便后面推导
-6、遍历dp数组填表：一个for循环遍历dp数组的未知位置，另一个for循环遍历硬币数组，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
+6、遍历dp数组填表：第一个for循环遍历dp数组的未知位置，第二个for循环遍历硬币数组，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
 7、返回结果：最后一个状态就是结果
  */
 class Solution {
@@ -67,4 +67,22 @@ public int coinChange(int[] coins, int amount) {
         }
         return (dp[amount] == amount + 1) ? -1 : dp[amount];
     }
+}
+
+
+/*
+其他同上。遍历dp数组填表：第一个for循环遍历硬币数组，第二个for循环遍历dp数组的未知位置，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
+ */
+class Solution {
+    public int coinChange(int[] coins, int amount) {
+        int[] dp = new int[amount + 1];
+        Arrays.fill(dp, amount + 1);
+        dp[0] = 0;
+        for (int coin : coins) {
+            for (int i = coin; i <= amount; i++) {
+                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
+            }
+        }
+        return (dp[amount] == amount + 1) ? -1 : dp[amount];
+    }
 }
diff --git a/leetcode_Java/Solution0416.java b/leetcode_Java/Solution0416.java
@@ -0,0 +1,81 @@
+// 416. 分割等和子集
+
+
+/*
+动态规划：0-1背包，必须先物品再背包，且逆序遍历背包
+1、题目：给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
+2、题目简化：求数组元素能否凑成和为sum(nums)/2
+3、数据校验：数组长度小于2、总和除以2余数不为0、元素最大值大于目标值，则不能分割
+4、定义dp数组：dp[i] 表示数组元素能否凑成和为 i
+5、状态转移方程：dp[i] = dp[i] || dp[i - num];
+6、初始化：dp[0] = true; 表示数组元素能否凑成和为0，方便后面推导
+7、遍历dp数组填表：第一个for循环遍历数组元素，第二个for循环逆序遍历dp数组的未知位置，根据条件获取dp数组的已知位置，
+   根据状态转移方程取已知结果汇总计算未知结果。逆序遍历是因为元素只用一次，如果正序遍历会导致元素重复使用。
+8、返回结果：最后一个状态就是结果
+ */
+class Solution {
+    public boolean canPartition(int[] nums) {
+        if (nums.length < 2) {
+            return false;
+        }
+        int sum = 0, maxNum = 0;
+        for (int num : nums) {
+            sum += num;
+            maxNum = Math.max(maxNum, num);
+        }
+        if (sum % 2 != 0) {
+            return false;
+        }
+        int target = sum / 2;
+        if (maxNum > target) {
+            return false;
+        }
+        boolean[] dp = new boolean[target + 1];
+        dp[0] = true;
+        for (int num : nums) {
+            for (int i = target; i >= num; i--) {
+                dp[i] |= dp[i - num];
+            }
+        }
+        return dp[target];
+    }
+}
+
+
+/*
+1、问题转化：一堆重量为nums[i]，价值也为nums[i]的物品中，能否恰好装满容量为target的背包
+2、定义dp数组：dp[i] 表示容量为i的背包最多能装的物品价值
+3、状态转移方程：dp[i] = Math.max(dp[i], dp[i - num] + num);
+                ↑                ↑               ↑
+    新状态,容量为i时最大价值   旧状态,不取num的价值   取num的价值
+4、初始化：初始化时默认都为0
+5、遍历dp数组填表：第一个for循环遍历数组元素，第二个for循环逆序遍历dp数组的未知位置，根据条件获取dp数组的已知位置，
+   根据状态转移方程取已知结果汇总计算未知结果。逆序遍历是因为元素只用一次，如果正序遍历会导致元素重复使用。
+6、返回结果：判断最后一个状态的值是否为目标值
+ */
+class Solution {
+    public boolean canPartition(int[] nums) {
+        if (nums.length < 2) {
+            return false;
+        }
+        int sum = 0, maxNum = 0;
+        for (int num : nums) {
+            sum += num;
+            maxNum = Math.max(maxNum, num);
+        }
+        if (sum % 2 != 0) {
+            return false;
+        }
+        int target = sum / 2;
+        if (maxNum > target) {
+            return false;
+        }
+        int[] dp = new int[target + 1];
+        for (int num : nums) {
+            for (int i = target; i >= num; i--) {
+                dp[i] = Math.max(dp[i], dp[i - num] + num);
+            }
+        }
+        return dp[target] == target;
+    }
+}
diff --git a/leetcode_Java/Solution0518.java b/leetcode_Java/Solution0518.java
@@ -2,15 +2,13 @@
 
 
 /*
-动态规划：
+动态规划：完全背包，先物品再背包是计算组合，先背包再物品是计算排列，必须正序遍历背包才能重复使用物品
 1、题目：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。
 2、题目简化：求凑成总金额amount的硬币组合数
 3、定义dp数组：dp[i] 表示凑成总金额i的硬币组合数
 4、状态转移方程：dp[i] += dp[i-coin]，即所有dp[i-coin]相加
 5、初始化：dp[0] = 1，表示凑成总金额0的硬币组合数为1，方便后面推导
-6、遍历dp数组填表：一个for循环遍历dp数组的未知位置，另一个for循环遍历硬币数组，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
-   1）外层for循环遍历硬币，内层for遍历金额，这种遍历顺序中dp[i]里计算的是组合数
-   2）外层for循环遍历金额，内层for遍历硬币，这种遍历顺序中dp[i]里计算的是排列数
+6、遍历dp数组填表：第一个for循环遍历硬币数组，第二个for循环遍历dp数组的未知位置，根据条件获取dp数组的已知位置，根据状态转移方程取已知结果汇总计算未知结果
 7、返回结果：最后一个状态就是结果
  */
 class Solution {
