Leshan normal programming competition 2020-e: divide stones [01 backpacks]

Title Description

Do you have n Stones of known weight W1,…,Wn.
Your task is ： Divide the stones into two piles , Minimize the difference between the sum of the two piles .

Input

first line , Enter the number of stones n(1≤n≤60)
The second line , Input n The weight of a stone W1,…,Wn( Positive integer ,1≤Wi≤100000).

Output

Output a number , Represents the minimum weight difference between the sum of the stones divided into two piles .

The sample input

5
5 8 13 27 14

Sample output

3

Tips

Only divided into such two piles , The sum of the first pile is 35, The sum of the second pile is 32, So the weight difference is 3
The first pile ：8 13 14
The second pile ：5 27

Ideas

Try to divide a pile into two piles equally , We can imagine it as a backpack , The capacity of this backpack is sum/2, Each weight is the weight in the title , The value and weight are the same . The title translates into 01 knapsack problem .
01 knapsack problem ： Yes n Items , They have their own size and value , There are backpacks of given capacity , How to maximize the total value of the items in your backpack ？

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200;
int w[MAXN], v[MAXN], dp[6000000 + 50];
void solve() {
    
    int n, sum = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
    
        scanf("%d", &w[i]);
        v[i] = 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]] + v[i]);
        }
    }
    printf("%d\n", sum - 2 * dp[sum / 2]);
}
int main() {
    
    solve();
    return 0;
}