Algorithm for 2 person fair division - Please Help -

[MarkDej]

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

explaination of the input.tx and output.txt:

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.

[ProgramArtist]

Hi,

do you want the code gurus to give you the entire algo? Then read the FAQ's.

Else:
Can you tell us what you've done so far? Have you got some idea? Where do you have a problem in solving this?

With regards
Programartist

[MarkDej]

Hi,

I've written a program in PASCAL, but it is not effiecient.
Is it allowed for me to show my source code here in the forum?

[Eri523]

Is it allowed for me to show my source code here in the forum?

Yes.

How else should we be able to tell you what's wrong with it? ;)

Please use code tags when posting code.

[MarkDej]

How to use the code tags?
If i use <code> ... </code>

then nothing happens, and prints it as it is <code> ... </code>

[MarkDej]

This is part of the code that i wrote in C instead of PASCAL:

for(i = 0; i <= totalNumberOfGifts; i++){
arrange[0][0][i] = 1;
}


for (i = 1; i <= totalNumberOfGifts; i++){
for (y = 0; y <= halfTotalValueOFGifts; y++){
for (x = 0; x <= halfTotalValueOfGifts; x++){
bTrueFalse = 0;
if ( arrange[x][y][i-1] ){
bTrueFalse = i;
}
else if ( arrayOfGifts[i] <= x && arrange[x-arrayOfGifts[i]][y][i-1]){
bTrueFalse = x;
}
else if ( arrayOfGifts[i] <= y && arrange[x][y-arrayOfGifts[i]][i-1]){
bTrueFalse = y;
}

arrange[x][y][i] = bTrueFalse;
}
}
}


I don't know why it's not working!!
Can you help me?

[ProgramArtist]

Hi,

Please show more of your code. We don't know how did you declare arrange. What type is it?

In c/c++ arrays start always with the index 0 (as contrasted with PASCAL).
Your first loop that's why is probably wrong:

for(i = 0; i <= totalNumberOfGifts; i++){
arrange[0][0][i] = 1;
}


should be (if totalNumberOfGifts is the count of the gifts):

for(i = 0; i < totalNumberOfGifts; i++){
arrange[0][0][i] = 1;
}


Your second loop looks like a c-implementation of a PASCAL like loop:
for (i = 1; i <= totalNumberOfGifts; i++){
Although it is possible to use i-1 as the index I would recommend to change that to a usual c/c++ array indexing loop.


And please explain a lttle bit more clear what you mean with "it's not working". Are there compiler errors? Are there runtime errors or assertions? Which one? Or does the program simply not what you expect?

With regards
Programartist

[MarkDej]

Hello Programartist,

The complete code is:



#include <stdio.h>
#include <string.h>
#include <math.h>



int main(){
int giftsTotalValue = 0;
int numberOfGifts = 0;
int aGift[] = {12, 45, 65, 3, 65, 87, 2, 34, 5, 7, 32, 1, 4, 99, 54};
int i;

for(i = 0; i < sizeof(aGift); i++){
numberOfGifts++;
giftsTotalValue += aGift[i];
}

int b1, b2;
int halfTotalValue = floor(giftsTotalValue/2);
int arrange[15][15][15];
int Bro1Gifts[15];
int Bro2Gifts[15];
int bTrueFalse;
int takenValue = 0;
int remainingValue = giftsTotalValue;


for(i = 0; i <= numberOfGifts; i++){
arrange[0][0][i] = 1;
}


for (i = 1; i <= numberOfGifts; i++){
for (b2 = 0; b2 <= halfTotalValue; b2++){
for (b1 = 0; b1 <= halfTotalValue; b1++){
bTrueFalse = 0;
if ( arrange[b1][b2][i-1] ){
bTrueFalse = i;
}
else if ( aGift[i] <= b1 && arrange[b1-aGift[i]][b2][i-1]){
bTrueFalse = b1;
}
else if ( aGift[i] <= b2 && arrange[b1][b2-aGift[i]][i-1]){
bTrueFalse = b2;
}

arrange[b1][b2][i] = bTrueFalse;
}
}
}


for (b1 = 0; b1 <= halfTotalValue; b1++){
if (arrange[b1][b1][numberOfGifts]){
takenValue = b1;
remainingValue = giftsTotalValue - b1 - b1;
}
}


b1 = takenValue;
b2 = takenValue;


for (i = numberOfGifts; i >= 1; i--){
if (arrange[b1][b2][i]==i ){ }
else if (arrange[b1][b2][i]==b1){
Bro1Gifts[i]=aGift[i];
b1 -= aGift[i];
}
else if (arrange[b1][b2][i]==b2){
Bro2Gifts[i]=aGift[i];
b2 -= aGift[i];
}
}



printf("remaining gifts total value = %d\n", remainingValue);
printf("Bro1 gifts total value = %d\n", takenValue);
printf("Bro2 gifts total value = %d\n", takenValue);




system("pause");
return 0;
}







and the result i get when compiling with DEV-C++:

remaining gifts total value = -725499503
Bro1 gifts total value = 0
Bro2 gifts total value = 0
Press any key to continue . . .


Looking forward to hearing from you.
MD

[nuzzle]

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!


From what I can see this is a variation on the Partition problem which is NP complete. It means there's no better way than to evaluate all possible combinations of gift sharing and then finally pick the best one.

http://en.wikipedia.org/wiki/Partition_problem

But there's also a simple heuristic algorithm which will give you a good approximate solution:

Think of the gifts as having a weight corresponding to their value. You sort all gifts according to weight. You then put the gifts on a balance scale one by one starting with the heaviest gift. You put gifts on one side until it tilts over. Then you put gifts on the other side until this side tilts over, etcetera. Each time the scale becomes evenly balanced you have a fair sharing so each brother gets the gifts on one side of the scale. The process continues until all gifts have been on the scale. If the scale never balances this algorithm won't come up with a completely fair solution so the brothers will have to fight it out in some other way. :)