#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2010
    Posts
    3
    Rep Power
    0

    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
  2. #2
  3. Transforming Moderator
    Devshed Supreme Being (6500+ posts)

    Join Date
    Mar 2007
    Location
    Washington, USA
    Posts
    14,143
    Rep Power
    9398
    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?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2010
    Posts
    3
    Rep Power
    0
    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.

IMN logo majestic logo threadwatch logo seochat tools logo