【算法与数据结构】1049、LeetCode 最后一块石头的重量 II-三、完整代码

# include <iostream>
# include <vector>
# include <numeric>
# include <algorithm>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        vector<int> dp(vector<int>(sum/2 + 1, 0));
        for (int i = 0; i < stones.size(); i++) {			// 遍历物品
            for (int j = sum/2; j >= stones[i]; j--) {			// 遍历背包容量
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum -2 * dp[sum/2];
    }
};

int main() {
    Solution s1;
    vector<int> stones = { 2,7,4,1,8,1 };
    int result = s1.lastStoneWeightII(stones);
    cout << result << endl;
    system("pause");
    return 0;
}

end