Click here to Skip to main content
15,901,001 members
Please Sign up or sign in to vote.
1.50/5 (2 votes)
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

1 solution

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
 
Share this answer
 
Comments
[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) ?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900