【力扣刷题|第十七天】0-1 背包 完全背包

目标和

力扣题目网址:目标和

这道题我们先用回溯的思想来做。首先我们设正数和为S，数组和为N，目标值为T，那么S-(N-S)=T化简之后可以得S=(T+N)/2即选择的正数个数为偶数，而且N+T也为偶数，那么第一个判断条件我们就有了，并且问题可以转换为，背包容量为(T+N)/2，有几种选择正数的方式能够填满背包，回溯思想代码如下，主要还是选或者不选，这里我们仍然需要用记忆化搜索，不然会超时

package day17;import java.util.Arrays;// p
// s-p
// p-(s-p)=target
// p = (s+target)/2
public class id_494_1 {public int[] NUMS;private int[][] memo;public int findTargetSumWays(int[] nums, int target) {target += Arrays.stream(nums).sum();if(target < 0 || target % 2 != 0) return 0;target /= 2;int n = nums.length;memo = new int[n][target + 1];for (int[] row : memo) {Arrays.fill(row, -1);}this.NUMS = nums;return dfs(NUMS.length - 1, target);}public int dfs(int i,int c){if(i < 0){return c == 0 ? 1 : 0;}if(memo[i][c] != -1) return memo[i][c];if(c < NUMS[i]){return memo[i][c] = dfs(i-1,c);}return memo[i][c] = dfs(i-1,c) + dfs(i-1,c-NUMS[i]);}
}

接下来我们用递推的方式来做也就是用循环和二维数组来代替递归,这道题的初始化也需要我们讨论，我们只需要初始化0 0处为1，因为背包容量为0的时候0个物品有1种添加方式，也就是不放物品。

package day17;import java.util.Arrays;public class id_494_2 {private int[][] f;public int findTargetSumWays(int[] nums, int target) {target += Arrays.stream(nums).sum();if(target < 0 || target % 2 != 0) return 0;target /= 2;int n = nums.length;f = new int[n+1][target + 1];f[0][0] = 1;for(int i = 0; i < n; i++){for(int j = 0; j < target+1; j++){if(j < nums[i]){f[i+1][j] = f[i][j];}else {f[i+1][j] = f[i][j] + f[i][j - nums[i]];}}}return f[n][target];}
}

简化为一个数组的时候，我们需要倒序遍历背包，具体解释可以看灵茶山艾府的视频背包问题:遍历顺序

package day17;import java.util.Arrays;public class id_494_3 {private int[] f;public int findTargetSumWays(int[] nums, int target) {target += Arrays.stream(nums).sum();if(target < 0 || target % 2 != 0) return 0;target /= 2;int n = nums.length;f = new int[target + 1];f[0] = 1;for(int i : nums){for(int j = 0; j < target + 1; j++){f[j] += f[j - i];}}return f[target];}
}

零钱兑换

力扣题目网址:零钱兑换

这道题和上一道差不多，但是这道题硬币可以重复选择。我们就不用回溯的思想来写了，直接看二维数组递推的方法。这道题需要我只有在00的地方初始化为0，其他地方初始化为int的最大值，但是在java中这样会越界，主播我初始化为20000，这样在最后如果找不到符合的，那么f[n][amount]的值就是我们初始化的值

package day17;import java.util.Arrays;// 完全背包
public class id_LCR103_2 {private int[][] memo;public int coinChange(int[] coins, int amount) {int n = coins.length;memo = new int[n + 1][amount + 1];for (int[] ints : memo) {Arrays.fill(ints, 20000);}memo[0][0] = 0;for(int i = 0; i < n; i++){for(int j = 0; j <= amount; j++){if(j < coins[i]){memo[i+1][j] = memo[i][j];}else {memo[i+1][j] = Math.min(memo[i][j], memo[i+1][j - coins[i]] + 1);}}}return memo[n][amount] < 20000 ? memo[n][amount] : -1;}}

我们继续简化为一维数组，这时候遍历循序就需要变为正序

package day17;import java.util.Arrays;public class id_LCR103_3 {public int coinChange(int[] coins, int amount) {int n = coins.length;int[] f = new int[amount + 1];Arrays.fill(f, 20000);f[0] = 0;for(int x : coins){for(int j = x; j <= amount; j++){f[j] = Math.min(f[j], f[j - x] + 1);}}return f[amount] < 20000 ? f[amount] : -1;}
}