最后一块石头的重量||
返回剩余最后一块石头石头最小的可能重量,那么就应该最后剩余的两块石头尽量都等于或接近总重量的一半,这样剩下的就是一半的质量
目标和
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
回溯的方法
class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {if (sum == target) {result.push_back(path);}// 如果 sum + candidates[i] > target 就终止遍历for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i + 1);sum -= candidates[i];path.pop_back();}}
public:int findTargetSumWays(vector<int>& nums, int S) {int sum = 0;for (int i = 0; i < nums.size(); i++) sum += nums[i];if (S > sum) return 0; // 此时没有方案if ((S + sum) % 2) return 0; // 此时没有方案,两个int相加的时候要格外小心数值溢出的问题int bagSize = (S + sum) / 2; // 转变为组合总和问题,bagsize就是要求的和// 以下为回溯法代码result.clear();path.clear();sort(nums.begin(), nums.end()); // 需要排序backtracking(nums, bagSize, 0, 0);return result.size();}
};
解释:假设加法的总和为x,那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target,x = (target + sum) / 2,且若(target+sum)%2!=0的话,x就是无解的
本题要求的,就是装满j的背包有多少种方案,
不放物品i:即背包容量为j,里面不放物品i,装满有dp[i - 1][j]中方法。
放物品i: 即:先空出物品i的容量,背包容量为(j - 物品i容量),放满背包有 dp[i - 1][j - 物品i容量] 种方法
如何初始化
最左上角的元素,如果背包容量为0,就放0种物品,所以就是1种方法,
最左列也应该是为0,但如果存在元素为0的情况,则如下
二维数组的代码
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(abs(target)>sum) return 0;if((target+sum)%2==1) return 0;int bagSize=(target+sum)/2;vector<vector<int>> dp(nums.size(),vector<int>(bagSize+1,0));if(nums[0]<=bagSize) dp[0][nums[0]]=1;dp[0][0]=1;int numZero=0;for(int i=0;i<nums.size();i++){if(nums[i]==0) numZero++;dp[i][0]=(int) pow(2.0,numZero);//最左列向下递增}for(int i=1;i<nums.size();i++){for(int j=0;j<=bagSize;j++){if(nums[i]>j) dp[i][j]=dp[i-1][j];else dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];}}return dp[nums.size()-1][bagSize];}
};
一维的方法初始化起来更简单
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 (abs(target) > sum) return 0; // 此时没有方案if ((target + sum) % 2 == 1) return 0; // 此时没有方案int bagSize = (target + sum) / 2;vector<int> 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];}
总结:在求装满背包有几种方法的情况下,递推公式一般为:dp[j]+=dp[j-nums[i]];
一和零
一道01背包问题,但这个背包有两个维度,一个是m,一个是n
dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。
注意!!!这里01背包都是从后往前遍历,因为是相当于两个一维动规的叠加
class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m+1,vector<int>(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];}
};