Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=503
Solution Idea:
In this problem given n coins where value of every coin is <=500. We have to divide this coins into two parts so that the difference between the sum of the values of coins in each parts is minimum.
To do this at first wile taking input we sum up all the coins value. and we can see that the maximum sum can be 50000 and if we divide it into two parts then one part can have maximum of 25000 sum. So we take a dp array size greater than 25000 and run coin change to make values from coins. after that we have to check which largest value we can make from the coins which is less than or equal to sum/2. where sum is the summation of all coins value.
Let the largest value we can make is X. so our output is (sum-X)-X or sum-2*x.
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/
#include <bits/stdc++.h>
#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define db double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define sqr(x) (x)*(x)
#define D(x) cout<<#x " = "<<(x)<<endl
#define VI vector <int>
#define DBG pf("Hi\n")
#define MOD 100007
#define MAX 10000
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a) (int)a.size()
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n) for(int i=0;i<n;i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define ull unsigned long long
using namespace std;
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/
bool dp[30000];
int coins[200];
int main()
{
///freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);
int t,n;
sf(t);
TEST_CASE(t)
{
int n,sum=0;
sf(n);
loop(i,n) sf(coins[i]),sum+=coins[i];
ms(dp,false);
int mid=(sum/2);
dp[0]=1;
loop(i,n)
{
for(int j=mid; j-coins[i]>=0; j--)
dp[j] |=dp[j-coins[i]];
}
for(int i=sum/2; i>=0; i--)
if(dp[i])
{
printf("%d\n",abs((sum-i)-i));
break;
}
}
return 0;
}