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;
}

Problem 67

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

int t;
long arr[5051];
bool flag[5051];

long sum(int i,int step)
{
if(i>5050)
return 0;

if(flag[i] == true)
return arr[i];

//cout<<i<<" "<<arr[i]<<endl;

long left = sum(i+step, step+1);
long right = sum(i+step+1, step+1);

arr[i] += max(left, right);
//cout<<i<<" "<<arr[i]<<endl;
flag[i] = true;
return arr[i];
}

int main()
{

freopen("in.txt","r",stdin);

memset(flag, 0, sizeof(flag));

int a, i=1;
t=1;
while(cin>>a)
{
arr[i] = a;
i++;
}

cout<<sum(1,1)<<endl;


//cout<<in<<endl;

return 0;
}

How to convert number to char array

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

int main()
{
char buf[20];

int a = 10;

sprintf(buf, "%d", a);

for(int I=0;I<log10(a)+1; I++){
cout<<buf[I]<<" ";
}
return 0;
}

Heap #4: HeapSort Descending Order

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

int Parent(int index)
{
return index>>1; // index/2
}

int LeftChild(int index)
{
return index<<1; // 2 * index
}

int RightChild(int index)
{
return (index<<1) + 1; // (2 * index) + 1
}

void Min_Heapify(int *x, int index, int heapsize)
{
//cout<<"Visit-->"<<index<<endl;
int left = LeftChild(index);
int right = RightChild(index);
int smallest = index;

if(left<=heapsize && x[left]<x[smallest])
{
smallest = left;
}

if(right<=heapsize && x[right]<x[smallest])
{
smallest = right;
}

if(smallest != index)
{
swap(x[smallest], x[index]);
Min_Heapify(x, smallest, heapsize);
}
}

void Build_Min_Heap(int *x, int heapsize)
{
for(int I=(heapsize/2); I>0; I--)
{
Min_Heapify(x, I, heapsize);
}
}

void HeapSort(int *x, int heapsize)
{
Build_Min_Heap(x, heapsize);

for(int I = heapsize; I>1; I-- )
{
swap(x[1], x[I]);
heapsize--;
Min_Heapify(x, 1, heapsize);
}
}


void printArray(int *x, int arraySize)
{
for(int I=0; I<arraySize; I++)
{
cout<<I<<" "<<x[I]<<endl;
}

cout<<endl;
}


int main()
{
//Heap start from index 1
int a[] = {-1,8,3,6,5,4,7,2};

int arraySize = sizeof(a)/sizeof(*a);

printArray(a, arraySize);
       
        //Descending Order
HeapSort(a, arraySize-1);

printArray(a, arraySize);


return 0;
}

Heap #3: HeapSort Ascending Order

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

int Parent(int index)
{
return index>>1; // index/2
}

int LeftChild(int index)
{
return index<<1; // 2 * index
}

int RightChild(int index)
{
return (index<<1) + 1; // (2 * index) + 1
}

void Max_Heapify(int *x, int index, int heapsize)
{
//cout<<"Visit-->"<<index<<endl;
int left = LeftChild(index);
int right = RightChild(index);
int largest = index;

if(left<=heapsize && x[left]>x[largest])
{
largest = left;
}

if(right<=heapsize && x[right]>x[largest])
{
largest = right;
}

if(largest != index)
{
swap(x[largest], x[index]);
Max_Heapify(x, largest, heapsize);
}
}

void Build_Max_Heap(int *x, int heapsize)
{
for(int I=(heapsize/2); I>0; I--)
{
Max_Heapify(x, I, heapsize);
}
}

void HeapSort(int *x, int heapsize)
{
Build_Max_Heap(x, heapsize);

for(int I = heapsize; I>1; I-- )
{
swap(x[1], x[I]);
heapsize--;
Max_Heapify(x, 1, heapsize);
}
}


void printArray(int *x, int arraySize)
{
for(int I=0; I<arraySize; I++)
{
cout<<I<<" "<<x[I]<<endl;
}

cout<<endl;
}


int main()
{
//Heap start from index 1
int a[] = {-1,2,3,9,5,6,7,8};

int arraySize = sizeof(a)/sizeof(*a);

printArray(a, arraySize);

//For Ascending order
HeapSort(a, arraySize-1);

printArray(a, arraySize);


return 0;
}

Heap #2: Build A MIN Heap

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

int Parent(int index)
{
return index>>1; // index/2
}

int LeftChild(int index)
{
return index<<1; // 2 * index
}

int RightChild(int index)
{
return (index<<1) + 1; // (2 * index) + 1
}

void Min_Heapify(int *x, int index, int heapsize)
{
//cout<<"Visit-->"<<index<<endl;
int left = LeftChild(index);
int right = RightChild(index);
int smallest = index;

if(left<=heapsize && x[left]<x[smallest])
{
smallest = left;
}

if(right<=heapsize && x[right]<x[smallest])
{
smallest = right;
}

if(smallest != index)
{
swap(x[smallest], x[index]);
Min_Heapify(x, smallest, heapsize);
}
}

void Build_Min_Heap(int *x, int heapsize)
{
for(int I=(heapsize/2); I>0; I--)
{
Min_Heapify(x, I, heapsize);
}
}

void printArray(int *x, int arraySize)
{
for(int I=0; I<arraySize; I++)
{
cout<<I<<" "<<x[I]<<endl;
}

cout<<endl;
}


int main()
{
//Heap start from index 1
int a[] = {-1,8,3,6,5,4,7,2};

int arraySize = sizeof(a)/sizeof(*a);

printArray(a, arraySize);

Build_Min_Heap(a, arraySize-1);

printArray(a, arraySize);


return 0;
}

Heap #1: Build A MAX Heap

If you want to understand the code fully please read Introduction to algorithm(CLRS) chapter-6 first.

#include<cstdio>

#include<iostream>

using namespace std;

int Parent(int index)

{

return index>>1; // index/2

}

int LeftChild(int index)

{

return index<<1; // 2 * index

}

int RightChild(int index)

{

return (index<<1) + 1; // (2 * index) + 1

}

void Max_Heapify(int *x, int index, int heapsize)

{

//cout<<"Visit-->"<<index<<endl;

int left = LeftChild(index);

int right = RightChild(index);

int largest = index;

if(left<=heapsize && x[left]>x[largest])

{

largest = left;

}

if(right<=heapsize && x[right]>x[largest])

{

largest = right;

}

if(largest != index)

{

swap(x[largest], x[index]);

Max_Heapify(x, largest, heapsize);

}

}

void Build_Max_Heap(int *x, int heapsize)

{

for(int I=(heapsize/2); I>0; I--)

{

Max_Heapify(x, I, heapsize);

}

}

void printArray(int *x, int arraySize)

{

for(int I=0; I<arraySize; I++)

{

cout<<I<<" "<<x[I]<<endl;

}

cout<<endl;

}

int main()

{

//Heap start from index 1

int a[] = {-1,2,3,4,5,6,7,8};

int arraySize = sizeof(a)/sizeof(*a);

printArray(a, arraySize);

Build_Max_Heap(a, arraySize-1);

//cout<<"--"<<heapsize<<endl;

printArray(a, arraySize);

return 0;

}