织梦音乐网站程序,中国园林网,昆明凡科建站公司,为哈尔滨网页设计制作第一题是最后一块石头的重量IIhttps://leetcode.cn/problems/last-stone-weight-ii/#xff0c;没啥思路#xff0c;直接上题解了。本题可以看作将一堆石头尽可能分成两份重量相似的石头#xff0c;于是问题转化为如何合理取石头#xff0c;使其装满容量为石头总重量一半的…第一题是最后一块石头的重量IIhttps://leetcode.cn/problems/last-stone-weight-ii/没啥思路直接上题解了。本题可以看作将一堆石头尽可能分成两份重量相似的石头于是问题转化为如何合理取石头使其装满容量为石头总重量一半的背包且每个石头只能取一次这样就变成了一个01背包问题。其中石头的重量与价值相同均为stones[i]。接下来按照动规五步曲进行分析dp[j]表示容量为j的背包中可以装的最大重量为dp[j]对于第i块石头可以取也可以不取故dp[j] max(dp[j], dp[j - stones[i]] stones[i])初始化dp 0先遍历物品再遍历背包即可。
class Solution {
public:int lastStoneWeightII(vectorint stones) {int sum 0;for (int i 0; i stones.size(); i){sum stones[i];}int target sum/2;vectorint dp(150001,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];}
};
第二题是目标和https://leetcode.cn/problems/target-sum/description/可以假设加法总和为x则减法总和为sum - x题中指出x- (sum - x) target可得x (target sum)/2。此时题目转化为要装满容量为x的背包共有几种方法且每个数的状态只能取一次再次转化为01背包问题。根据动规五步曲确定dp[j]表示装满容量为j背包的方法数量为dp[j]。当遍历到元素i时想知道dp[j]的值必须先知道背包中去掉numbers[i]时dp数组的值由此反复得到dp[j] dp[j - numbers[i]]。初始化将dp[0] 1说实话我不是特别理解。遍历顺序依然是先物品后背包背包从后往前遍历。
class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for (int i 0; i nums.size(); i){sum nums[i];}if ((target sum) % 2 1) return 0;if (abs(target) sum) return 0;int bagsize (target sum) / 2;vectorint dp(bagsize 1, 0);dp[0] 1;for (int i 0; i nums.size(); i){for (int j bagsize; j nums[i]; j--){dp[j] dp[j - nums[i]];}}return dp[bagsize];}
};
事实上该题的二维数组解法更为好懂将其贴在下面第三题是一和零https://leetcode.cn/problems/ones-and-zeroes/description/本题的背包维度有两个m和n即如何选取元素使元素满足0、1的个数要求。利用动规五步曲dp[i][j]为拥有i个0j个1的元素个数。dp[i][j]可由去掉上一个字符串时dp[i - 0nums][j - 1nums]得出即dp[i][j] max(dp[i][j], dp[i - 0nums][j - 1nums] 1)。由题意可知dp数组初始化为0即可dp[0][0]0也符合认知。遍历顺序依然不变。
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0));for (string str : strs){int onenum 0, zeronum 0;for (char c : str){if (c 0) zeronum;else onenum;}for (int i m; i zeronum; i--){for (int j n; j onenum; j--){dp[i][j] max(dp[i][j], dp[i - zeronum][j - onenum] 1);}}}return dp[m][n];}
};
由此可见背包问题的维度一般有以下几种在给定背包容量的情况下装满背包的最大价值能否装满装满背包的方法数量装满时背包中物品数量尽可能装满的重量。
