桂林网站建设兼职深圳外企公司排名如何查询？

桂林网站建设兼职,深圳外企公司排名,织梦模板使用教程,wordpress自定义登录页背包问题 下图将背包问题做了分类 其中之重点#xff0c;是01背包#xff0c;即一堆物件选哪样不选哪样放入背包里。难度在于#xff0c;以前的状态转移#xff0c;多只用考虑一个变量#xff0c;比如爬楼梯的阶层#xff0c;路径点的选择#xff0c;这也是能用滚动数组…背包问题 下图将背包问题做了分类 其中之重点是01背包即一堆物件选哪样不选哪样放入背包里。难度在于以前的状态转移多只用考虑一个变量比如爬楼梯的阶层路径点的选择这也是能用滚动数组表示动态规划的原因而现在要同时考虑两个物品和背包容量。 01背包 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。 使用动态规划五部曲 1 - 确定dp数组含义有一种写法 是使用二维数组即dp[i] [j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。 2 - 到了第 i 件物品的时候背包容量为 j 但就放不放物品两种选择 不放第 i 件物品那么背包容量不变从dp[i - 1] [j]状态而来放第 i 件物品那么就会从dp[i - 1] [j - weight[i]]状态而来因为至少得有足够的空间将物品放进去才行。 所以递归公式 dp[i] [j] max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] value[i]); 3 - 初始化dp数组如果是01背包的话背包容量如果为零那么价值也一定为零。而能放入第一件物品的时候就是其对应的价值。 4 - 遍历顺序这一步比较重要在初期理解01背包的时候会显得有一点难以理解。但总归记住就是一个二维数组和之前的题目一样先遍历物品再遍历背包容量物品固定尝试一点点把物品塞进去和先遍历背包容量再遍历物品背包容量固定尝试能塞进去哪个都是可以的。 从数组的角度考虑这一点也是可以的根据递推公式当前状态是从数组的左上角位置而来只要保持是这个方向就可以了。就和我们之前求解路径问题时一样。 5 - 举例推导 假设背包最大重量为4。 物品为 重量价值物品0115物品1320物品2430 那么数组的最终状态就如下图所示 关于01背包也有使用一维数组即滚动数组的方法。其核心思想是如果不放物品dp[j]其实就是自己本身如果要放物品那么dp[j] 就是考虑从一个能放下这个物品的背包塞入该物品即dp[j - weight[i]] value[i]。 遍历顺序就是不能是从一个空背包开始放了而是从一个满的背包里尝试取出某件物品这样做是为了保证物品只被放入一次。这么做也是有现实依据的就是先考虑所有能用得上的东西再从这些物品里挑出来不是那么重要的物品。 我私认为注重理论推导就可以在后期的解题过程中方便不少但是也不必过于纠结能否“记住理论”还是要投入实际应用才能更好的理解理论。 接下来进入解题过程。 416 分割等和子集 medium 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。 为什么说动态规划难呢我认为是不少时候压根意识不到该用动态规划求解问题。 关于这道题首先要想到要对整个数组求和如果和是奇数咋分都分不出来。 如果是偶数那么所有数之和的一半就是我们期望的“背包最大容量”剩下的事情就是把数字填进去就可以了和01背包完全一样。 根据这个思想代码如下 bool canPartition(vectorint nums) {int sum 0;for (int num: nums)sum num;if (sum % 2 1) return false;int target sum / 2;vectorint dp(10001, 0); // 题目中给出数组长度最大是200值最大是100取总和的一半肯定够了// 我们采用先遍历数字的方式for (int i 0; i nums.size(); i) {for (int j target; j nums[i]; --j) {dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}return dp[target] target; }1049 最后一块石头的重量 II medium 有一堆石头用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。