November 22nd, 2010, 02:18 AM
Algorithm for 2 person fair division - Please Help -
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!
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.
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
10 3 12 5 15 6
4 2 1
November 22nd, 2010, 03:11 AM
Uh, what? Where'd the 5, 10, and 12 go? Where'd the 1, 2, and 4 come from?
10 3 12 5 15 6
4 2 1
November 22nd, 2010, 03:29 AM
the input.txt has 2 lines
Originally Posted by requinix
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.