0
$\begingroup$

Given a sequence of N activity durations, the time P of pause between activities, and D, the length of a day (there are no breaks between days, only between activities in a day), what is the minimum sum of the cube loss across all days and how many days are required for the solution. The activities need to be scheduled in order, so the first day will have the first x activities, the second day will have the next y activities, and so on. Between activities that take place in the same day there is a pause time P.

Example:

N = 4

P = 2

D = 7

Activities durations : 3 2 2 5

In this example the minimum total cubed loss would be:

(7 - 3)^3 + (7 - 2 - 2)^3 + 0^3 = 65

The last day doesn't contribute to the total cubed loss (in total the activities are distributed in 3 days). Even if we could have added the second activity to the first day, the total cubed loss would be higher:

(7 - 3 - 2 - 2)^3 + (7 - 2)^3 + 0^3 = 125

I have tried an greedy algorithm but the solution is not optimal. I think the optimal solution can be obtained using a dynamic programming approach. How can I build the solution matrix?

I have tried building a matrix where row i contains the sums of i consecutive activity durations + i - 1 pauses. I am stuck with this approach on how should I traverse the matrix in order to get the optimal result.

Any help is appreciated.

$\endgroup$
  • $\begingroup$ Why is $(7-2)^3$ in the second equation? Shouldn't it be $(7-5)^3$? $\endgroup$ – xskxzr Apr 12 '18 at 14:59
  • $\begingroup$ No, 7 is the length of the day, 3 is the first activity followed by a 2 that represents a pause between two activities (the 3 and the 2) and then the second activity with the cost of 2 so that implies (7 - 3 - 2 - 2). $\endgroup$ – Temp Email Apr 12 '18 at 15:33
  • $\begingroup$ What about the two 2s in the first equation? Must there be a pause between any two consecutive activity durations? You can edit the question to clarify these things. $\endgroup$ – xskxzr Apr 12 '18 at 15:37
  • $\begingroup$ Yes there is a pause time between activities that take place in the same day, example : 3 activities with a duration of 1 would mean 1 + 2 + 1 + 2 + 1 (total duration). $\endgroup$ – Temp Email Apr 12 '18 at 15:42
  • $\begingroup$ What does "cube loss" mean? How is it defined? Please define all terms/concepts that you use, in the question. $\endgroup$ – D.W. Apr 13 '18 at 3:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.