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

将题目转换为，把一堆石头分成两堆,求两堆石头重量差最小值
所以只要求将一堆stone放进最大容量为sum/2的背包,求放进去的石头的最大重量，记为MaxWeight，则另一堆石头的重量为sum-MaxWeight，最终答案即为sum-2*MaxWeight;、

  1. class Solution {
  2. public:
  3.     int lastStoneWeightII(vector<int>& stones) {
  4.         vector<int> dp(15001, 0);
  5.         int sum = 0;
  6.         for (int stone:stones) sum += stone;
  7.         int target = sum / 2;
  8.         for (int stone:stones) { // 遍历物品
  9.             for (int j = target; j >= stone; j--) { // 遍历背包
  10.                 dp[j] = max(dp[j], dp[j - stone] + stone);
  11.             }
  12.         }
  13.         return sum - dp[target] - dp[target];
  14.     }
  15. };