LeetCode 1049. 最后一块石头的重量 II**

很难得一道题。。。一环扣一环，我是傻逼。

刚开始想的是选取每次选取最大值抵消结果无解；

第二次想的是每次求离均值最大的两个元素进行抵消，但是发现还是不太行；

官方给的答案是整体加上正负号求序列和，使得结果的绝对值最小；

例如，对于a,b,c,d四块石头，可以挑选(a,c),(d,b)，相当于(a-c),(d-b)，但是还要将这两块石头加入，还要在前面加正负号，但是这样展开还是相当于在所有元素前加入正负号，因此可以分为两组，第一组为被减数，第二组减数，只有当两组数相差足够小，才能满足绝对值最小；

所以如果有sum总和，只要求出被其中一组，就可以得到另一组，也就可以得到最终结果；

其中较小的一组必定是不大于sum/2的最大和；

所以这个问题变成了，从1～n个元素中挑选，得到不大于sum/2的最大值；

背包容量为sum/2，背包价值为当前最大值，物品个数为1～n；

class Solution {
public:
    int lastStoneWeightII(vector& stones) {
        int n=stones.size();
        int sum=0;
        for(auto& ele:stones){
            sum+=ele;
        }
        int target=sum/2;
        vector>dp(n,vector(target+1,0));
        for(int i=stones[0];i<=target;i++){
            dp[0][i]=stones[0];
        }
        for(int i=1;i
            for(int j=0;j<=target;j++){
                if(j
                    //放不下；
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=max(dp[i-1][j-stones[i]]+stones[i],dp[i-1][j]);
                }
            }
        }
        return sum-dp[n-1][target]-dp[n-1][target];
    }
};