Lesson: 4
Problem: 562
Title: Dividing coins
Difficulty Level: 2
Date: Dec 14, 2008
Site: UVA
Some coins with different values are given; you have to divide those coins among two persons in such way that the difference between the amounts each person obtains should be minimized.
Consider the 1st sample input:
3
2 3 5
3 coins are given, summation is: 2 + 3 + 5 = 10. So each person should get 10/2 = 5, and we can easily make it..
2 3 for 1st person and 5 for 2nd person. Now come the 2nd case..
4
1 2 4 6
Here summation is 13. We can not make an even division, so we shall try to make the 2nd most fair division. For this case we can make 6/7 division( 6 for 1st person, 1+2+4 = 7 for 2nd person), and the difference is 7 - 6 = 1.
So, we will follow this procedure..
Let N is the summation of all given coins.
1. We shall try to make N/2 using each coin if possible.
2. If we fail, then we will try to make N/2-1, if fail then N/2-2....
note that we can not use a coin more than once.
How can we solve this ? do we need to know any algorithm ?
Answer: we do not need to know any algorithm, believe me. Like you, i have no deep knowledge of algorithm.
Then what is the way to solve ? let's we try..
Consider 2nd sample input:
4
1 2 4 6
sum = 1 + 2 + 4 + 6 = 13. we can not make even division. so we can try ( 1 + 2 + 4 + 6) / 2 - 1 = 6 to make.
Take an array, say Division[100].
Set Division[0] = 1;
At very first, take first coin, 1.
Traverse the array from index 6 to 0. if any index contains a value 1, set Division[index+1] = 1, in this case, you will find only index 0. so set Division[0 + 1] = 1.
why 0 + 1 ? 0 is the index number where Division[index] = 1 and '1' is the 1st coin which value = 1.
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
After doing the above tasks, we get Division[0] = 1 and Division[1] = 1. That means using only first coin we can make 0 and 1.
Next the 2nd coin, it's 2.
Do the same. This time index 1 and 0 contain value 1. So set Division[1+2] = 1 and Division[0+2] = 1.
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Now have a close look at the array after the above 2 steps.
Divison[0] = 1
Divison[1] = 1
Divison[2] = 1
Division[3] = 1
and the remaining cells contain 0.
What does it mean ? It means that we can make either 0, 1, 2 or 3 using the first 2 coins ( 1,2)
After the process 3rd coin( 4) , the array will look like:
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
And finally using the 4th coin(6) , the array will be:
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
if index + coin_value > 6, we will ignore this case. why ? think yourself.
Next we will find the best result. Traverse the array again from index 6 to 1. if any cell contains 1, stop there. Here we get 6. That means we can make 6 using given coins.
What is the result ? i think you already figure it out.
Summation is: 1+2+4+6 = 13. we can make 6, i.e other person will get 13-6 = 7, and the difference is 7-6 = 1. Clear??
Check my source code, how to handle the input and how to implement this procedure.
Hmmm damn, i apology to cheat you. i have promised not to use any algorithm, but we use a dynamic algoritm. And more bad news, if you get this procedure properly, you are very close to another two dp algorithms, coin change and knapsack problem.
Important note: input may contain 100 coins and each coin has a value of maximum 500 cent. so array size should be (100*500)/2 plus few more.