互助网站建设,国外网站国内备案,珠海最新消息今天,建站到网站收录到优化背包问题
下图将背包问题做了分类 其中之重点#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。那么粉碎的可能结果如下 如果 x y那么两块石头都会被完全粉碎 如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。 最后最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下就返回 0。 实不相瞒以我现在的水平看到这道题我还是想不到应该用动态规划来做但是多少有点儿那个味儿了。
要使最后剩下的石块重量尽可能小就需要能撞掉的石头尽可能多所以这道题可以看成是背包容量为[总重量/2]向下取整物品价值就是石头重量的0-1背包问题。
求解方式和上面的题几乎一模一样代码如下
int lastStoneWeightII(vectorint stones) {int totalWeight 0;for (int stoneWeight: stones)totalWeight stoneWeight;vectorint dp(15001, 0);int target totalWeight / 2;for (int i 0; i stones.size(); i) {for (int stonesWeight target; stonesWeight stones[i]; --stonesWeight) {dp[stonesWeight] max(dp[stonesWeight], dp[stonesWeight - stones[i]] stones[i]);}}return totalWeight - 2 * dp[target];
}说到这里可能还是有人不太明白为什么能这么写之所以要尽量的往总数量一半的背包里塞就说明这些都是希望能尽量被撞掉的可以证明如果能达到一半的容量那么其必然可以全部被撞掉所以最后要减去2倍的dp[target]。
