Timus Online Judge 1005. Stone Pile——01背包好题

题目

1005. Stone Pile @ Timus Online Judge

就是给你一组堆石头，分成两组，叫你求两组重量差的最小值

思路

这道题解法很巧妙，用01背包来解决

dp[i][j]: 表示前i个物品里面，花费代价小于等于j能获得的价值最大值，这里的代价为石头重量，价值也为石头重量。这样处理了后 dp[n][sum/2] (sum为石头重量和)， 就表示让每堆石头重量更接近sum/2的最大价值。我们只有让每堆石头更接近sum/2, 那么差才最小

代码

/*
 * @Descripttion:
 * @Author: Echo
 * @version:
 * @Date: 2022-08-27 14:40:28
 * @LastEditors: Echo
 * @LastEditTime: 2022-08-27 17:41:45
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+9;
int dp[N],w[N];
int main()
{
    int n;
    cin>>n;
    int  sum=0;
    for(int i=1; i<=n; ++i){
        cin>>w[i];
        sum+=w[i];
    }
    for(int i=1; i<=n; ++i){
        for(int j=sum/2; j>=w[i]; --j){
            dp[j] = max(dp[j], dp[j-w[i]]+w[i]);
        }
    }
    cout<<sum - 2*dp[sum/2];
    return 0;
}

/*
5
30 45 12 23 8
7
2 1 9 8 4 2 5
 */