高端网站建设968,到做任务的网站上面推广粉象生,迁安建设局网站,建设工程查询扣分网站### 9.9 01背包问题#xff08;一维二维#xff09; 背包问题分类#xff1a;01背包#xff08;一种物品只有一个#xff09;#xff0c;完全背包#xff08;一种物品有无数个#xff09;#xff0c;多重背包#xff08;不同物品有不同数量#xff09;
46. 携带研究…### 9.9 01背包问题一维二维 背包问题分类01背包一种物品只有一个完全背包一种物品有无数个多重背包不同物品有不同数量
46. 携带研究材料第六期模拟笔试 题目描述 小明是一位科学家他需要参加一场重要的国际科学大会以展示自己的最新研究成果。他需要带一些研究材料但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等它们各自占据不同的空间并且具有不同的价值。 小明的行李空间为 N问小明应该如何抉择才能携带最大价值的研究材料每种研究材料只能选择一次并且只有选与不选两种选择不能进行切割。 输入描述 第一行包含两个正整数第一个整数 M 代表研究材料的种类第二个正整数 N代表小明的行李空间。 第二行包含 M 个正整数代表每种研究材料的所占空间。 第三行包含 M 个正整数代表每种研究材料的价值。 输出描述 输出一个整数代表小明能够携带的研究材料的最大价值。
暴力解法每个物品只有取和不取用回溯算法枚举就可以。时间复杂度n2 01背包问题 二维 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 https://www.bilibili.com/video/BV1cg411g7Y6 dp[i][j]:i 来表示物品、j表示背包容量 dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 如dp[1][4] 表示什么意思呢? 任取物品0、物品1放入容量为4的背包中最大价值是dp[1][4]。
二维数组遍历顺序先遍历物品再遍历背包/先遍历背包再遍历物品都可以。因为需要的值就是正上方和左上角的值。
遇到的问题 非leetcode包装好的方法需要获取数据 写的时候也有一些细节需要注意 java import java.util.Scanner; public class bag01TwoDimensional { public static void main(String[] args) { Scanner sc new Scanner(System.in); int num sc.nextInt(); int bagCapacity sc.nextInt(); int[] materialSpace new int[num]; int[] materialValue new int[num]; for (int i 0; i num; i) { materialSpace[i] sc.nextInt(); } for (int i 0; i num; i) { materialValue[i] sc.nextInt(); } //dp初始化 int[][] dp new int[num][bagCapacity1]; //初始化第一行有简洁的写法即直接从materialSpace[0]开始遍历。如果它大于包的容量则不进入循环。 for (int i materialSpace[0]; i bagCapacity; i) { dp[0][i] materialValue[0]; } //初始化第一列其实不用写默认的初始值就是0 for (int i 1; i num; i) { for (int j 0; j bagCapacity; j) { // //不要第i个物品 // int noI dp[i-1][j]; // //要第i个物品 // int withI dp[i-1][j-materialSpace[i]] materialValue[i]; if(materialSpace[i] j){ dp[i][j] dp[i-1][j]; }else{ dp[i][j] Math.max(dp[i-1][j], dp[i-1][j-materialSpace[i]] materialValue[i]); } } } // for (int i 0; i num; i) { // for (int j 0; j bagCapacity; j) { // System.out.print(dp[i][j] dp[i][j] ); // } // System.out.println(); // } System.out.println(dp[num-1][bagCapacity]); } } 01背包问题 一维 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-2.html
https://www.bilibili.com/video/BV1BU4y177kY
把矩阵压缩成一行把上一层拷贝到下一层。滚动数组。 1.确定dp数组dp table以及下标的含义 dp[j] 容量为j的背包能装进物品的最大价值。
2.确定递推公式 不放物品idp[j] 放物品idp[j-weight[i]]value[i]
3.dp数组如何初始化0/1确认很有讲究很重要 dp[0] 0;
4.确定遍历顺序 倒序遍历。如果正序遍历会导致前面的物品被反复加入
5.打印dp数组动态规划代码简短直接看打印出来的dp数组是不是和自己设想的一致 java public class bag02OneDimensional { public static void main(String[] args) { // int materialNum 6; // int capacity 6; // // int[] weight {2,2,3,1,5,2}; // int[] value {2,3,1,5,4,3}; //get data Scanner sc new Scanner(System.in); int materialNum sc.nextInt(); int capacity sc.nextInt(); int[] weight new int[materialNum]; int[] value new int[materialNum]; for (int i 0; i materialNum; i) { weight[i] sc.nextInt(); } for (int i 0; i materialNum; i) { value[i] sc.nextInt(); } int[] dp new int[capacity1];//当背包容量为i时包内物品的最大价值为dp[i] for (int i 0; i materialNum; i) { for (int j capacity; j weight[i]; j--) { int withoutI dp[j]; int withI dp[j-weight[i]] value[i]; dp[j] Math.max(withoutI,withI); //System.out.println(dp[i][j] dp[j]); } } System.out.println(dp[capacity]); } }
### 9.10 416. Partition Equal Subset Sum Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise. https://leetcode.cn/problems/partition-equal-subset-sum/description/ 416. 分割等和子集 本题是 01背包的应用类题目 https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html https://www.bilibili.com/video/BV1rt4y1N7jE
01背包里面的元素能不能刚好装满容量为数组元素和二分之一的背包。 物品的重量和价值相同
动态规划五部曲 1.确定dp数组dp table以及下标的含义 dp[j]:背包总容量为j放进物品后背的最大重量为dp[j]。
2.确定递推公式
3.dp数组如何初始化0/1确认很有讲究很重要 4.确定遍历顺序 后序遍历
5.打印dp数组动态规划代码简短直接看打印出来的dp数组是不是和自己设想的一致
自己做的时候错误点 没有剪枝。当总和为奇数时直接返回false即可。 java public class partitionEqualSubsetSum { 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[] dp new int[target 1]; //先遍历物品后遍历背包 for (int i 0; i nums.length; i) { for (int j target; j nums[i]; j--) { // int withI dp[j - nums[i]] nums[i]; // int withoutI dp[j]; dp[j] Math.max(dp[j - nums[i]] nums[i],dp[j]); } } return dp[target] target; } } class partitionEqualSubsetSumTest{ public static void main(String[] args) { int[] nums {1,2,3,5}; partitionEqualSubsetSum example new partitionEqualSubsetSum(); System.out.println(example.canPartition(nums)); } }
### 9.11 1049. Last Stone Weight II You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x y. The result of this smash is: If x y, both stones are destroyed, and If x ! y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x. At the end of the game, there is at most one stone left. Return the smallest possible weight of the left stone. If there are no stones left, return 0. https://leetcode.cn/problems/last-stone-weight-ii/description/ 1049. 最后一块石头的重量 II 本题就和 昨天的 416. 分割等和子集 很像了可以尝试先自己思考做一做。 https://www.bilibili.com/video/BV14M411C7oV https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html
把石头尽量分成重量相近的两堆比如总重量为23的石头堆分成11和12。
java public class lastStoneWeight2 { public int lastStoneWeightII(int[] stones) { int sum 0; for (int i 0; i stones.length; i) { sum stones[i]; } int target sum/2; int[] dp new int[target1]; for (int i 0; i stones.length; i) { //如果此时背包剩余容量小于待加入石头的重量则没必要进入循环 //If the remaining capacity of the backpack at this time is less than the weight of the stones to be added, there is no need to enter the loop for (int j target; j stones[i]; j--) { dp[j] Math.max(dp[j],dp[j-stones[i]] stones[i]); } } //return Math.abs(dp[target]-(sum-dp[target])); return sum - 2*dp[target]; } } class lastStoneWeight2Test{ public static void main(String[] args) { lastStoneWeight2 example new lastStoneWeight2(); int[] nums {31,26,33,21,40}; System.out.println(example.lastStoneWeightII(nums)); } }
### 9.12 494. Target Sum You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols and - before each integer in nums and then concatenate all the integers. For example, if nums [2, 1], you can add a before 2 and a - before 1 and concatenate them to build the expression 2-1. Return the number of different expressions that you can build, which evaluates to target. https://leetcode.cn/problems/target-sum/description/ 494. 目标和 大家重点理解 递推公式dp[j] dp[j - nums[i]]这个公式后面的提问 我们还会用到。 https://www.bilibili.com/video/BV1o8411j73x https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html
分成两个子集加法在一个子集(left)减法在一个子集(right)。
sum left right left sum - right target left - right left target right 2left sum target left (sumtarget)/2 如果不能整除就是凑不成target直接返回0 有多少种情况可以装满背包就返回多少 nums [1,1,1,1,1], target 3
dp[j] : 装满容量为j的背包有dp[j] 种方法
背包里已有 物品1: 有dp[4] 种方法凑成dp[5]; 物品2: 有dp[3] 种方法凑成dp[5];
递推公式 dp[j] dp[j-num[i]];
初始化dp[0] 1;
java public class targetSum { public int findTargetSumWays(int[] nums, int target) { int sum 0; for (int i : nums) { sum i; } //如果target的绝对值大于sum那么无解 if ((sum target) % 2 1 || Math.abs(target) sum) return 0; int capacity (sum target) 1; int[] dp new int[capacity 1]; dp[0] 1; for (int i 0; i nums.length; i) { for (int j capacity; j nums[i]; j--) { dp[j] dp[j-nums[i]]; } } return dp[capacity]; } } class targetSumTest { public static void main(String[] args) { targetSum example new targetSum(); int[] nums {1,1,1,1,1}; int target 3; System.out.println(example.findTargetSumWays(nums, target)); } }
### 9.13 474. Ones and Zeroes You are given an array of binary strings strs and two integers m and n. Return the size of the largest subset of strs such that there are at most m 0s and n 1s in the subset. A set x is a subset of a set y if all elements of x are also elements of y. https://leetcode.cn/problems/ones-and-zeroes/description/ 474.一和零 通过这道题目大家先粗略了解 01背包完全背包多重背包的区别不过不用细扣因为后面 对于 完全背包多重背包 还有单独讲解。 https://www.bilibili.com/video/BV1rW4y1x7ZQ https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html
装满容器最多多少个物品 m个0 n个1 凑成子集 背包最多有m个0n个1。装满这个背包最多有多少个物品 dp[i][j] 装满i个0j个1的背包最多有dp[i][j]个物品
待加入物品有x个0y个1 dp[i][j] Math.max((dp[i-x][j-y] 1),dp[i][j])
初始化 dp[0][0] 0; 非零坐标也初始化为0。防止递推公式求出的值被初始值覆盖。
java public class onesAndZero { public int findMaxForm(String[] strs, int m, int n) { int[][] dp new int[m 1][n 1]; //iterate items first for (String s : strs) { int x 0; int y 0; //to get how many 0 and i in this element char[] chars s.toCharArray(); for (char c : chars) { if (c 0) { x; } else { y; } } //and then iterate the bag for (int i m; i x; i--) { for (int j n; j y; j--) { dp[i][j] Math.max((dp[i - x][j - y] 1), dp[i][j]); } } } return dp[m][n]; } } class onesAndZeroTest { public static void main(String[] args) { onesAndZero example new onesAndZero(); String[] strs {10,0,1}; int m 1; int n 1; System.out.println(example.findMaxForm(strs,m,n)); } }
