November 22nd, 2010, 02:18 AM

Algorithm for 2 person fair division  Please Help 
Hi everybody
I am a beginner in the subject of algorithms, and i seek some help in finding the proper algorithm to solve the following problem:
Two brothers received together some gifts. They know the value of each gift, which is a positive integer.
They want to divide the gifts according to their values, so that the total value of the gifts that each of them receives are equal.
They realized that this can not necessarily be done for all the gifts, therefore, they accept to share some of the gifts that will remain , but these shared gifts should have the least possible values.
Write a program that gives a fair sharing!
Input specification:
In the input.txt file, the first row contains the number of gifts n which can be 1 <= n <= 80.
The second row contains n positive integers separated by spaces, these integers are the values of each gift.
Output specification:
In the output.txt file, the first row should contain the total value (sum) of the remaining gifts (shared gifts).
The second row should contain integers separated by spaces and these integers represent the position order of the gifts that one brother received.
The third row should contain integers separated by spaces and these integers represent the position order of the gifts that the other brother received.
Program can be written with any of the following languages:
C, C++, JAVA or PASCAL
Time limit: 0.5 seconds
Memory limit: 64MB
Example :
input.txt
6
10 3 12 5 15 6
output.txt
15
6 3
4 2 1
November 22nd, 2010, 03:11 AM

Code:
input.txt
6
10 3 12 5 15 6
output.txt
15
6 3
4 2 1
Uh, what? Where'd the 5, 10, and 12 go? Where'd the 1, 2, and 4 come from?
November 22nd, 2010, 03:29 AM

Originally Posted by requinix
Code:
input.txt
6
10 3 12 5 15 6
output.txt
15
6 3
4 2 1
Uh, what? Where'd the 5, 10, and 12 go? Where'd the 1, 2, and 4 come from?
the input.txt has 2 lines
first one has the total number of the gifts; in this case 6 gifts.
second line has the value of each one: gift1=10, gift2=3, gift3=12, gift4=5, gift5=15, gift6=6.
in the output.txt
the first row contains the sum of the remaining gift's values, which should have the least possible value that will not be given to any of the persons: in this case the only remaining gift is gift5 which has a value=15
the second row contains the gifts taken by one of the persons:
in this case; gift6, gift3
the third row contains the gifts taken by the other:
in this case; gift4, gift2, gift1.
so each person took total value of 18.
and they share gift5 which has a value of 15.
Sorry for the poor explanation.