Algorithm that schedule the right number of tasks to maximize reward: tough or basic?

Question

In the ith week, you have the choice of:

• doing nothing
• doing an basic task with a reward bi
• doing an tough task with a reward ti

If you choose to do a tough task, you must have 'done nothing' in the previous week [i-1]

What tasks must we choose we do to maximize reward? We can assume bi and ti are > 0.

---

My attempt

A greedy solution that I designed is to compare t_2 and b_1+b_2, it t_2 is higher, do nothing and on the next week do a tough task; if not, do basic tasks. Keep on doing this procedure until the end. Unfortunately, this does not obtain the optimal solution.

---

Does anyone have some sort of idea of an algorithm that obtains the optimal solution?

Thanks in advance!

Answer 1

I suggest to use the Dynamic Programming technique to tackle this problem as it is more straight-forward and intuitive. The setup of the DP is as follow:

Let P[i] denotes the optimal reward from week 1 till week i, then we have the following recurrence relation:

P[i] = max{ P[i-2] + ti, P[i-1] + bi } for i ≥ 2.

And the base cases are P[0] = 0, P[1] = b1 (assume you can only do basic task in week 1).

Update

Proof of optimality. Observe that the optimal solution P[i] must consists of either bi or ti (the contrapositive statement can be proved easily).

In the case P[i] uses bi, the best possible solution is P[i] = P[i - 1] + bi (because by definition P[i - 1] is the optimal solution). On the other hand, if P[i] uses ti, then the best possible solution is P[i] = P[i - 2] + ti.