leecode1049.最后一块石头的重量||
这道题目和416.分割等和子集有点像，本质就是将石头尽可能地分割成两个等份，二者的差值就是最后一块石头的最小重量
转换到01背包问题就是重量和价值都为stones[i]，背包容量为sum/2的背包所能获取的最大容量，最后只需要sum-dp[bagWeight]-dp[bagWeight]就能得到结果，由于sum/2是向下取整的，所以分割出来的这一份dp[bagWeight]是重量较小的那一份，所以最后相减的结果不会出现负数
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int n=stones.size(),sum=0,bagWeight=0;
for(int i=0;i<n;i++)
sum+=stones[i];
bagWeight=sum/2;
vector<int> dp(bagWeight+1,0);
for(int i=0;i<n;i++)
for(int j=bagWeight;j>=stones[i];j--)
dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
return sum-dp[bagWeight]-dp[bagWeight];
}
};