UVA 562

Important lines of this problem:

• Two Dutch tried to divide a bag with coins between the two of them
• They always wanted a fair share to the very last cent.
• Given a bag with a maximum of 100 coins
• The value of a coin varies from 1 cent to 500 cents
• Difference between the amount each person obtains should be minimised.
• It's not allowed to split a single coin.

How to Solve:

First divide the total amount of money to two people. Take the result as capacity of one people. Then run 0-1 knapsack on it with this capacity.
After that we will get first man money.
Second man money = Total money - first man money.

calculate the difference of money between them.

Code:

//Author: Faiem
//Email: faiem.ict@gmail.com
//03-02-2015

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

#define fr(limit) for(int I=0;I<limit;I++)
int dpState[100][50001];

class DividingCoins{

private:

int coin[100];
int maxCapacity, totalMoneyOfTwoPerson, n, calculateFirstPersonTotalMoney;

int CalculateMoney(int currentCoinNumber, int totalMoney)
{
if(currentCoinNumber >= n)
return 0;

if(dpState[currentCoinNumber][totalMoney] != -1)
return dpState[currentCoinNumber][totalMoney];

int profit1 = 0, profit2 = 0;

if(totalMoney + coin[currentCoinNumber] <= maxCapacity)
{
///next Coin = currentCoinNumber + 1
profit1 = coin[currentCoinNumber] + CalculateMoney(currentCoinNumber + 1, totalMoney + coin[currentCoinNumber]);

}

profit2 = CalculateMoney(currentCoinNumber + 1, totalMoney);

return dpState[currentCoinNumber][totalMoney] = max(profit1, profit2);
}

int Differnece(int x, int y)
{
if(x>y)
return x-y;
return y-x;
}

public:

DividingCoins(int m)
{
memset(dpState, -1, sizeof(dpState));
n = m;
totalMoneyOfTwoPerson = 0;
TakeInputAndSolvetheProblem(m);
}

void TakeInputAndSolvetheProblem(int m)
{
fr(m)
{
cin>>coin[I];
totalMoneyOfTwoPerson += coin[I];
}
maxCapacity = totalMoneyOfTwoPerson / 2 ;
calculateFirstPersonTotalMoney = CalculateMoney(0, 0);
}

int Output()
{
int calculate2ndPersonMoney = totalMoneyOfTwoPerson - calculateFirstPersonTotalMoney;
return Differnece(calculateFirstPersonTotalMoney, calculate2ndPersonMoney);
}
};


int main()
{
int T,m;
cin>>T;
while(T--)
{
cin>>m;
DividingCoins d(m);
cout<<d.Output()<<endl;
}
return 0;
}