Skip to content

Instantly share code, notes, and snippets.

@mariohuq
Last active October 22, 2021 19:58
Show Gist options
  • Save mariohuq/7bf68de19c948009ab3e2bbd53f7acda to your computer and use it in GitHub Desktop.
Save mariohuq/7bf68de19c948009ab3e2bbd53f7acda to your computer and use it in GitHub Desktop.
#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;
}

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment