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.
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.