Algorithm for efficient optimization

Question

I'm trying to make algorithm for optimization daily task schedule. For example:

1. There are 16 tasks to finish in one day, expirience worker can finish 8 tasks and newer worker could finish 4 tasks. As output we should get 2 expirienced worker and none new worker.

For now I have this code, but it's not working properly:

private void calculate(int numberOfTasks, int oldWorkerValue, int youngWorkerValue) { int numberOfOldWorkers = numberOfTasks / oldWorkerValue; int numberOfYoungWorkers = 0; if(numberOfOldWorkers == 0) { numberOfOldWorkers = 1; } else { numberOfYoungWorkers = (numberOfTasks % numberOfOldWorkers) / youngWorkerValue; if(numberOfTasks % oldWorkerValue != youngWorkerValue*numberOfYoungWorkers) { numberOfYoungWorkers = numberOfYoungWorkers + 1; } } System.out.println("Expirienced worker: " + numberOfOldWorkers + " and new workers: " + numberOfYoungWorkers); }

it returns me number of worker but it doesn't work like it should be. I don't get result like I wrote in this few examples. Could you give me some advice for this?

@Andreas beacuse in this case all workers give maximum. 10 + 3*6 = 28 — ankerr
– ankerr, Commented Jul 11, 2019 at 18:32
Yeah, sorry, I missed the "minimize overcapacity" on first read through. — Andreas
– Andreas, Commented Jul 11, 2019 at 18:33
If there are 17 tasks, as output we should get 2 expirienced worker. this gives us 2*10 = 20, why can't we use 3 new workers, this will be only 18? — Iłya Bursov
– Iłya Bursov, Commented Jul 11, 2019 at 18:40
@IłyaBursov because there always must be at least one experienced worker in team and because of that better solution is with two experienced worker. I will edit my question — ankerr
– ankerr, Commented Jul 11, 2019 at 18:44

Iłya Bursov · Accepted Answer · 2019-07-11 18:59:54Z

1

I'm not sure whether you can find exact formula for this, so I'd do simple brute force:

public static Pair<Integer, Integer> calculate(int numberOfTasks, int oldWorkerValue, int youngWorkerValue) { int m = Integer.MAX_VALUE; // minimal value int o = 0; // old workers int n = 0; // new workers for (int i = 1; i <= (int)Math.ceil((double) numberOfTasks / oldWorkerValue); i++) { int nw = (int) Math.ceil((double)(numberOfTasks - i * oldWorkerValue) / youngWorkerValue); if (nw < 0) nw = 0; int tm = i * oldWorkerValue + nw * youngWorkerValue; if (tm < m) { m = tm; o = i; n = nw; } } return new Pair<>(o, n); // pair <old workers, new workers> }

answered Jul 11, 2019 at 18:59

Iłya Bursov

24.4k4 gold badges36 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

ankerr Over a year ago

everything works great, but can you pls explain me a little bit more this code, because i've never working with brute force, and also this first line confuse me, you write comment minimal value but you take max integer value

Iłya Bursov Over a year ago

brute force just checks all possible variants and finds minimal work usage, this minimal usage is stored in variable m, but initial values - maximal possible, to simplify condition in loop

ankerr Over a year ago

thank you, and just one question. I've make test with 100 tasks and as result it return 1 experienced and 15 new workers, and I expect it would return 10 experienced workers. Is this ok?

Iłya Bursov Over a year ago

@ankerr you see, both answers are technically correct, this algorithm tries to minimize number of experience workers (in case of multiple minimal solutions overall), but if you change if (tm < m) { to if (tm <= m) {, it will try to maximize it instead

Collectives™ on Stack Overflow

Algorithm for efficient optimization

1 Answer 1

4 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Related