balanced_partition_diff.cpp

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> weights(n);

    for (int i = 0; i < n; i++)
    {
        cin >> weights[i];
    }

    int sum = accumulate(weights.begin(), weights.end(), 0);
    int half_sum = sum / 2;

    vector<vector<int>> max_subset_sum(2, vector<int>(half_sum + 1));
    for (int& m : max_subset_sum[0])
    {
        m = 0;
    }
    
    for (int i = 1; i <= n; i++)
    {
        const int w = weights[i - 1];
        for (int j = 0; j < w && j <= half_sum; j++)
        {
            max_subset_sum[i % 2][j] = max_subset_sum[(i - 1) % 2][j];
        }
        for (int j = w; j <= half_sum; j++)
        {
            max_subset_sum[i % 2][j] = max(max_subset_sum[(i - 1) % 2][j], max_subset_sum[(i - 1) % 2][j - w] + w);
        }
    }

    int max_achievable_sum = max_subset_sum[n % 2][half_sum];
    cout << (sum - max_achievable_sum) - max_achievable_sum;
    return 0;
}

description.md

1005. Stone Pile

Time limit: 1.0 second
Memory limit: 64 MB

You have a number of stones with known weights w[1], ..., w[n]. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Input

Input contains the number of stones n (1 ≤ n ≤ 20) and weights of the stones w[1], ..., w[n] (integers, 1 ≤ w[i] ≤ 100000) delimited by white spaces.

Output

Your program should output a number representing the minimal possible weight difference between stone piles.

Sample

input	output
5 5 8 13 27 14	3

Problem Source: USU Championship 1997