How should Alice spend $5$ days on $3$ tasks?

Question

Alice has $5$ days that she can spend on $3$ tasks. The benefit of spending a certain number of days on each task is given by the following table. Alice seeks to maximize benefit.

      |      Benefit of n days spent on task
 Task |   0   |   1   |   2   |   3   |   4   |   5
------+-------+-------+-------+-------+-------+-----
  T_1 |  10   |  45   |  50   |  55   |  55   |  60
  T_2 |  35   |  40   |  45   |  50   |  50   |  55
  T_3 |  25   |  40   |  60   |  65   |  70   |  80

Is there an optimization algorithm that could be used to prune the search space? Or is an exhaustive search required in order to find the optimal solution?

The benefit would always be $\geqslant 0$ and would always be monotonically increasing.

Answer 1

The first thing to simplify the details would be to remove the baseline values - you can re-express it all as $total\_value = 70 + v_1 + v_2 + v_3$, with values from:

      |      Benefit of n days spent on task
 Task |   0   |   1   |   2   |   3   |   4   |   5
------+-------+-------+-------+-------+-------+-----
  v_1 |   0   |  35   |  40   |  45   |  45   |  50
  v_2 |   0   |   5   |  10   |  15   |  15   |  20
  v_3 |   0   |  15   |  35   |  40   |  45   |  55

We could write this as a bunch of fancy dependent marginal values, but the table is small enough that we probably won't get a huge gain from that. Instead, we can at least improve our search by finding a lower bound by just taking a greedy approach - for each day, find the choice of task that gives us the greatest marginal improvement on our value.

Which in this case starts with task 1 (35 value on the first day versus 5 or 15), then 2 days of task 3 (15 and 20 value against 5). At this point, all options give us 5 value for the next two days of effort, so regardless of our choice we'll get 10 more value. So the total value we get is $total\_value = 70 + 35 + 15 + 20 + 5 + 5 = 150$.

From there, you can eliminate some possibilities by noting that, for example, it's impossible to do better than that by just doing one task for all 5 days, so you must have some kind of mixed strategy. You could even do a few different baselines to prove whether avoiding one task entirely has any benefit.

Answer 2

For this example, a greedy algorithm actually provably produces the optimal result. (And the proof does not require exhaustive search.)

Observation: If every task has non-increasing marginal returns, then a greedy algorithm would be optimal: On each day, just pick the task that gives the (by then) global max marginal return.

In fact, Stronger Observation: if a greedy algorithm finds a sub-optimal solution, then it must have "missed" a high-valued, increasing marginal return (because it never picked the smaller marginal returns before it).

The given numbers don't satisfy non-increasing marginal returns, but the exceptions (i.e. the increasing marginal returns, marked *) are few enough:

      |      Marginal Returns
 Task |   0   |   1   |   2   |   3   |   4   |   5
------+-------+-------+-------+-------+-------+-----
  T_1 |  10   | +35   |  +5   |  +5   |   0   |  +5*
  T_2 |  35   |  +5   |  +5   |  +5   |   0   |  +5*
  T_3 |  25   | +15   | +20*  |  +5   |  +5   | +10*

In this example, we can prove that all the exceptions don't matter. First of all, looking back at the original table, we see that spending just $1$ day per task (total gain $125$) outperforms spending all $5$ days in any single task (total gain $55, 60$ or $80$), so the optimal solution does not involve the $5$th column. This took care of almost all the increasing marginal returns.

The only increasing marginal return left is the $+20$ on day $2$ of $T_3$. Lets run the greedy algorithm. It picks, in succession:

• $T_1$ for a day, $+35$

• $T_3$ for a day, $+15$

• $T_3$ for another day, $+20$

• For the final two days, it has many choices, all of which are tied at $+5$ per day.

So: since it picked the only remaining increasing marginal return (the $+20$), this means the result is provably optimal. The answer is $70 + 35 + 15 + 20 + 5 + 5 = 150$.

Answer 3

The greedy algorithm is good, but it may not give the optimal solution, because it makes optimal choice at each step rather than the overall path.

Since on the day $0$ all the benefits are given for free, we can reduce the table: $$\begin{array}{c|cccc} Task&1&2&3&4&5\\ \hline T_1&35&40&45&45&50\\ T_2&5&10&15&15&20\\ T_3&15&35&40&45&55 \end{array}$$ Consider all options: $$\begin{array}{c|c|c} (T_1,T_2,T_3)&Benefit&Benefit\\ \hline (5,0,0)&50+0+0&50\\ (4,1,0)&45+5+0&50\\ (4,0,1)&45+0+15&60\\ (3,2,0)&45+10+0&55\\ (3,1,1)&45+5+15&65\\ (3,0,2)&45+0+35&70\\ (2,3,0)&40+40+0&\color{red}{80}\\ (2,2,1)&40+10+15&65\\ (2,1,2)&40+5+35&\color{red}{80}\\ (2,0,3)&40+0+40&\color{red}{80}\\ (1,4,0)&35+15+0&50\\ (1,3,1)&35+15+15&65\\ (1,2,2)&35+10+35&\color{red}{80}\\ (1,1,3)&35+5+40&\color{red}{80}\\ (1,0,4)&35+0+45&\color{red}{80}\\ (0,5,0)&0+20+0&20\\ (0,4,1)&0+15+15&30\\ (0,3,2)&0+15+35&50\\ (0,2,3)&0+10+40&50\\ (0,1,4)&0+5+45&50\\ (0,0,5)&0+0+55&55 \end{array}$$ Hence, the maximum benefit is: $70+80=150$. Note that there are $6$ different options to gain this total benefit.

If $40$ units (not $5$) were added on day $5$ for Task 1, then $(5,0,0)$ would be $85+0+0=85$ and $70+85=155$ would be the optimal solution. And it would be missed by the greedy algorithm.