首页 > 分享 > 背包系列问题详解

背包系列问题详解

萌宠菠菠乐园
2024-09-14 23:20

背包问题

0-1背包问题题目
给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 weight[i]，价值为 value[i]，现在让你用这个背包装物品，最多能装的价值是多少？

样例： N = 3, W = 4 wt = [2, 1, 3] val = [4, 2, 3] 结果： 6 解释：选择前两件物品装进背包，总重量 3 小于 W，可以获得最大价值 6。 12345678 Java代码实现模板：

public class Main{ public static void main(String[] args) { //N代表物品的数量，M代表背包的容量 int N=3,M=4; int[] weight={2,1,3}; int[] value={4,2,3}; //定义动态规划的数组，dp[i][w]代表前i个物品，当前背包容量为w，这种情况下可以装的最大的价值是dp[i][w] int[][] dp = new int[N + 1][M + 1]; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if(weight[i-1]>j){ //第i个物品的重量大于容量j，选择不装入 dp[i][j]=dp[i-1][j]; }else{ //在装入和不装入中选择最优的 dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1]); } } } System.out.println(dp[N][M]); /* * 单纯的求解背包能装的最大的容量就已经结束 * 下面的代码是求出了装入的物品具体的号码是哪一个 * */ boolean[] isAdd = new boolean[N+1]; for (int i = N; i>= 1;i--){ if (dp[i][M] == dp[i-1][M]) isAdd[i] = false; else{ isAdd[i] = true; //最大重量-当前重量...求剩余重量 M -= weight[i-1]; } } for (int i = 1; i <=N; i++) { if(isAdd[i])System.out.println("物品序号："+i); } } }

12345678910111213141516171819202122232425262728293031323334353637 子集背包问题题目：
输入一个只包含正整数的非空数组 nums，请你写一个算法，判断这个数组是否可以被分割成两个子集，使得两个子集的元素和相等。

输入 nums = [1,5,11,5]，算法返回 true，因为 nums 可以分割成 [1,5,5] 和 [11] 这两个子集。输入 nums = [1,3,2,5]，算法返回 false，因为 nums 无论如何都不能分割成两个和相等的子集。 12 Java代码实现模板

public class Main{ public static void main(String[] args) { int[] nums = new int[]{1,3,2,5}; int sum=0; for (int num : nums) sum += num; // 和为奇数时，不可能划分成两个和相等的集合 if (sum % 2 != 0) { System.out.println(false); return; } int n = nums.length; sum = sum / 2; boolean[][] dp = new boolean[n + 1][sum + 1]; //初始化，背包没有空间的时候就相当于装满了 for (int i = 0; i <= n; i++) dp[i][0] = true; for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { if (j - nums[i - 1] < 0) { // 背包容量不足，不能装入第 i 个物品 dp[i][j] = dp[i - 1][j]; } else { // 装入或不装入背包 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]; } } } System.out.println(dp[n][sum]); } }

123456789101112131415161718192021222324252627282930 代码优化，二维dp数组变一维

public class Main{ public static void main(String[] args) { int[] nums = new int[]{1,3,7,5}; int sum = 0; for (int num : nums) sum += num; // 和为奇数时，不可能划分成两个和相等的集合 if (sum % 2 != 0) { System.out.println(false); return ; } int n = nums.length; sum = sum / 2; boolean[] dp = new boolean[sum + 1]; // base case dp[0] = true; for (int i = 0; i < n; i++) { for (int j = sum; j >= 0; j--) { if (j - nums[i] >= 0) { dp[j] = dp[j] || dp[j - nums[i]]; } } } System.out.println(dp[sum]); } }

123456789101112131415161718192021222324252627 完全背包题目
给定不同面额的硬币 coins 和一个总金额 amount，写一个函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。样例

输入 amount = 5, coins = [1,2,5] 算法应该返回 4，因为有如下 4 种方式可以凑出目标金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 123456 Java代码实现

public class Main{ public static void main(String[] args) { int[] coins = new int[]{1,2,5}; int amount = 5; int n = coins.length; int[][] dp =new int[n + 1][amount + 1]; // 初始化，背包容量为0，可以装满 for (int i = 0; i <= n; i++) dp[i][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= amount; j++) if (j - coins[i-1] >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]]; else dp[i][j] = dp[i - 1][j]; } System.out.println(dp[n][amount]); } }

1234567891011121314151617181920 代码优化，二维dp数组变一维

public class Main{ public static void main(String[] args) { int[] coins = new int[]{1,2,5}; int amount = 5; int n = coins.length; int[] dp = new int[amount + 1]; dp[0] = 1; // base case for (int i = 0; i < n; i++) for (int j = 1; j <= amount; j++) if (j - coins[i] >= 0) dp[j] = dp[j] + dp[j-coins[i]]; System.out.println(dp[amount]); } } 1234567891011121314