15,901,001 members
See more:
A few days back, I asked by my teacher to find a solution in the following problem.

Three brothers have a shop.They know the total profit of the shop in the upcoming days. The brothers agreed that they would divide the total time in three successive parts, not necessarily equal
duration, and that each one will be working in the shop and during one of these parts to collect the corresponding profit on his behalf.
But they want to make a deal fairly, so that one not to received from more profit
from someone else. Specifically, they want to minimize the
profit will receive the most "favored" of the three.

We want to find the profit of the more "favored" brother. We know the days and the profit of every day. The first number in the input file is the number of K days and the follow K numbers which is the profit of every day.

Εg of input : 8 5 6 1 4 9 3 1 2

Eg of output is 13.

The first brother profit is 5+6+1=12. The second brother profit is
4+9=13. The third brother profit is 3+1+2=6..

So we must find a flexible work hour for each brother and his salary and then to write the biggest salary in a file.

Here what I did so far:

Question
How can I make an algorythm that can find the days of work of evry employee cause mine isn't very efficient and isn't the right one. I just pass so much time to think about it and I can't find a solution. Has someone any idea?

Here is the code :

C
```#include <stdio.h>
#include <stdlib.h>

void write_output(FILE* output,int money) {
output = fopen("share.out","w+");
fprintf(output,"%d\n",money);
fclose(output);

}

int main() {

FILE *input,*output;

int days = 0, sum = 0;
input = fopen("share.in","r");

fscanf(input,"%d",&days);

int *salary = (int *)malloc(days * sizeof(int));

for (int i = 0; i < days; i++){
fscanf(input,"%d", &salary[i]);
sum += salary[i];
}
fclose(input);

int average_salary = (sum / 3);

/************************************/
for (int i = 0; i < days; i++){
printf("%d\n", salary[i]);
}
/*****************************************************/

int first = 0, second = 0, third = 0, i = 0;

while (first <= average_salary) {
first += salary[i];
i++;
}

int position_last_first = i ;

while (second <= average_salary) {
second += salary[i];
i++;
}

int position_last_second = i ;

while (i < days) {
third += salary[i];
i++;
}

/****************************************************/

int big = 0;
int nfirst = first, nsecond = second, nthird = third;

if (first > second) {
if(first > third) {
big = first;
nfirst = first + salary[position_last_first];
nsecond = second - salary[position_last_first];

}
else {
big = third;
nthird = third - salary[position_last_second];
nfirst = first + salary[position_last_second];

}
}
else {
if(second > third) {
big = second;
nfirst = first + salary[position_last_first];
nsecond = second - salary[position_last_first];

}
else {
big = third;
nthird = third - salary[position_last_second];
nsecond = nsecond + salary[position_last_second];

}
}

if (nfirst > nsecond) {
if(nfirst > nthird) {
write_output(output, nfirst);
}
else {
write_output(output, nthird);
}
}
else {
if(nsecond > nthird) {
write_output(output, nsecond);

}
else {
write_output(output, nthird);
}
}

free(salary);
return 0;
}```
Posted

## Solution 1

For small numbers, you might calculate all permutations and weight each permutation with the largest share. The minimum of the largest share (not necessarily only one) is the best choice according to your criterions.
E.g.

ABCweight
561 4 9 3 1 220
56 14 9 3 1 219
56 1 49 3 1 215
56 1 4 93 1 220
56 1 4 9 31 223
56 1 4 9 3 1224
5 614 9 3 1 219
5 61 49 3 1 215
5 61 4 93 1 214
5 61 4 9 31 217
5 61 4 9 3 1218
5 6 149 3 1 215
5 6 14 93 1 213
5 6 14 9 31 216
5 6 14 9 3 1217
5 6 1 493 1 216
5 6 1 49 31 216
5 6 1 49 3 1216
5 6 1 4 931 225
5 6 1 4 93 1225
5 6 1 4 9 31228

This is far from optimal, but it will result in all possible solutions and you can chose the (one) minimal one.
The number of permutations is:
- given: 3 brothers, N numbers
- permutations: 1+0.5*N*(N-3)
- E.g. N=8 --> permutations = 1+0.5*8*5 = 21
- E.g. N=20 --> permutations = 1+0.5*20*17=171

Now you need to define an algorithm that creates the permutations.

A possible algorithm gives to each permutation a unique id, e.g. 1,1,6 is A=1, B=1, C=6 numbers, i.e. the first permutation of the table above. In the given case, 3,2,3 is the optimum.
E.g. a crude algorithm that keeps the last minimal solution could be implemented as follows
```N = ...
Salary[0...N-1] = ...
Min = Sum(Salary[0...N-1])
Permutation = [0,0,0]
for A=1 to N-2 do loop
for B=1 to N-1-A do loop
ProfitA = Sum(Salary[0...A-1])
ProfitB = Sum(Salary[A...A+B-1])
ProfitC = Sum(Salary[A+B...N-1])
ProfitMax = Max(ProfitA, ProfitB, ProfitC)
if Min is greater than ProfitMax then
Min = ProfitMax
Permutation = [A,B,C]
end if
end loop
end loop
Print Min : Permutation```
Only then you should start writing C code.
I leave this as exercise to implement in C.

Cheers
Andi

[no name] 1-Feb-15 6:44am
ok I undesrand. But the maxinum salary of each day is 100.000.000 and the sum of all days would not be up to 1.000.000.000. Also I want my code to run in 1sec. Thats the restrictions which I fall upset and couldn't solve my problem.
Andreas Gieriet 1-Feb-15 6:55am
So, use the appropriate value type.
Andi
[no name] 1-Feb-15 6:58am
so even with that type of numbers (long long) the programm could run in 1s?
Andreas Gieriet 1-Feb-15 7:05am
Does not depend on the size of the type, depends on the number of permutations. How many days are you expected to calculate and how large is the overall sum at max.
This is your task to determine and model your solution accordingly. An optimizing algorithm is only good for certain constraints. Optimization is *always* expensive, since you normally have to visit all entities, calculate some weight function, may need some searching/sorting, etc.
See There ain't no such thing as a free lunch ;-)
Cheers
Andi
[no name] 1-Feb-15 6:46am
Which is your complexity? O(n^2) ?