本文主要是介绍代码随想录算法训练营第四十二天|LeetCode1049、LeetCode494 目标和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题1:
指路:1049. 最后一块石头的重量 II - 力扣(LeetCode)
思路与代码:
本题中,我们要让剩下的石头重量尽可能小,那么每次就要尽可能找重量相等或最相近的两个石头,如果我们把两个石头分别放入两个数组内,再继续按照重量找尽量相等的石头,此时我们发现,两个数组内的元素和趋于相等,也就是两个数组的元素和尽量等于原数组和的一半,像极了第二题 分割等和子集。与之不同的是需要返回剩下的石头重量。那么我们再顺一遍(注意本题中依旧是石头的重量与价值的意义相同)。尽量将一个子集凑成原数组元素和的一半,一个元素最多取一次,01背包问题。首先,定义一个数组dp[j],其含义为一个容量为j的背包,所放物品最大的价值是dp[j];其次,我们确定递推公式,01背包的递推公式是,放物品i的价值和不放物品i的价值的较大值,也就是dp[j]=max(dp[j], dp[j - stones[i]] + stones[i]);然后我们进行初始化,当背包的容量也就是j为0时放不进任何东西,最大价值自然是0,当容量非0时,既要满足常理不为负数,也要保证后面的值不被初始值覆盖,所以也要初始化为0。此处我们假设一个极端情况,当所有的石头共30块重量皆为最大值100,此时原数组总和为最大值3000,但我们求的是一个子集到达原和的一半,所以此处在无溢出的情况下初始为dp(1501, 0);接着,我们确定遍历顺序,在此处两个for循环,外层遍历物品i,内层j遍历背包(注意,01背包内层顺序为倒序,完全背包内层顺序为正序,)。最后我们打印出结果,这里求的是剩下的重量,我们用其中一堆的重量sum-stones[target]减去另一堆stones[target]的重量即可,也就是sum-stones[target]-stones[target]。代码如下:
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(); int sum = 0; // stones数组的元素和for (int i = 0; i < stones.size(); i++) {sum += stones[i];}int target = sum / 2; // 要达到的数// 定义一个dp数组,容量为j的背包盛放的最大价值(重量)是dp[j] vector<int>dp (1501, 0);for (int i = 0; i < stones.size(); i++) { // 物品for (int j = target; j >= stones[i]; j--) { // 背包dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}return (sum - dp[target] - dp[target]);}
};
题2:
指路:494. 目标和 - 力扣(LeetCode)
思路与代码:
对于这个题,我们将整数和负数分开放,求得原数组的元素和之后,如果原和减去正数和等于target则符合条件。又因为其中的元素只使用一次,归为01背包问题类。首先,定义一个数组dp[j],其含义为填满j容量的背包,有dp[j]种方法。其次我们确定递推公式,当数值为nums[i]时,则有dp[j-nums[i]]种方法。这里要注意一个特殊情况,当target=5而nums[i]为2时无法得到结果,所以当target+sum与2的余数不为0时没有结果。然后进行初始化,我们将大小为正数个+1的dp数组初始化为0,当j=0时方法为1种。接着确定遍历顺序,依旧是外层物品正序(此处物品是正数),内层背包倒序(此处为正数个数大小的背包)。最后打印即可。
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i]; // 得到数组和}if (sum < abs(target)) return 0;if ((target + sum) % 2 == 1) return 0;// 例如target=5,nums=2int t = (target + sum) / 2;vector<int> dp(t + 1, 0); // dp[0] = 1;for (int i = 0; i < nums.size(); i++) { // 物品for (int j = t; j >= nums[i]; j--) { // 背包//dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i]] + nums[i]);dp[j] += dp[j - nums[i]] ;} }return dp[t];}
};
这篇关于代码随想录算法训练营第四十二天|LeetCode1049、LeetCode494 目标和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!