0
$\begingroup$

Here is the problem statement. Let $E_1,...,E_n$ be a set of $n$ exercises, each taking 1 day to solve, and suppose we have $n$ days available to solve the exercises. Each exercise $E_i$ has a deadline $D[i]$ associated to it, which is an integer in the range $0...n - 1$. Each exercise $E_i$ must either be solved on a day $d$ with $d \leq D[i]$ (so that it meets its deadline) or it should not be solved at all. When we solve exercise $E_i$, we receive $P[i]$ points. The goal is to compute a schedule for solving exercises such that the total number of points scored is maximised.

To solve the problem I follow a greedy strategy. Working backwards, starting from day $n$, I choose the exercise with the maximum number of points achievable whose deadline has not passed yet and decrement $n$ by one, then find the next exercise with the maximum number of points whose deadline has not passed yet and so on.

We prove this strategy results in an optimal solution. Let $d$ be the current day and $s^*$ be the exercise which gives the most points whose deadline has not passed yet, so $D[s^*] \geq d$. Let $OPT$ be the optimum solution, i.e. the maximum number of points achievable. We consider two cases. The first being that $s^*$ is in the optimum solution $OPT$. In this case we are done. Now, we consider the case where $s^*$ is not in the optimum solution $OPT$. Let $s'$ be different from $s^*$ and $s' \in OPT$. Now we replace $s'$ with $s^*$ to construct another solution $OPT^*$:

$OPT^* = OPT - P[s'] + P[s^*]$

Then, since $P[s'] \leq P[s^*]$ we have that:

$OPT^* \geq OPT$

And so by choosing exercise $s^*$ instead of $s'$ we can improve the solution $OPT$ to $OPT^*$, contradicting the fact that $OPT$ is optimal. And so $OPT$ must contain exercise $s^*$. This concludes the proof.

Now, what could possible alternative approaches be to solving this problem? For example, a solution using the greedy stays ahead approach would be welcome or another variant of the cut and paste method. Also, if there are any errors with the reasoning it would be appreciated if these are pointed out :).

I have implemented a backtracking algorithm as well as the greedy algorithm and found the solutions coincide so it has been experimentally verified that the greedy strategy works. However I would like to know for sure that it does, which is why I asked the question.

Other greedy strategies, such as starting from day one and choosing the exercise which gives the maximum number of points whose deadline has not passed yet gives suboptimal solutions. Counter examples can readily be found.

For those who are interested the pseudocode for the greedy algorithm is given below:

func(D[], P[]) {
    
    n = D.size();
    
    vis[];

    for(int i = 0; i < n; i++)
        vis[i] = false;
    
    maxPoints = 0;
    
    for(int d = n - 1; d >= 0; d--) {
        points = 0;
        index = -1;
        for(int i = 0; i < n; i++) {
            if(D[i] >= d and vis[i] == false) {
                if(P[i] >= points) {
                    index = i;
                    points = P[i];
                }
            }
        }
        if(index != -1)
            vis[index] = true;
        maxPoints = maxPoints + points;
    }
    
    return maxPoints;
}

This problem comes from an algorithms course: https://www.win.tue.nl/~kbuchin/teaching/2IL15/

The problem set itself can be found at: https://www.win.tue.nl/~kbuchin/teaching/2IL15/Homework/hw-A1.pdf

The author of the problem set is Kevin Buchin.

Improve this question
$\endgroup$
7
  • $\begingroup$ Your "proof" is almost correct. However, it could not be considered as rigorous. For example, it does not handle the case when $P(s')=P(s^*)$ correctly. For example, it is not clear where your "proof" use the critical requirement that the strategy must work "backwards, starting from day $n$". $\endgroup$
    – John L.
    Mar 11 at 20:11
  • $\begingroup$ Put it in another way, although your "proof" presents the exchange technique, which is the most convincing evidence why your greedy strategy works, a rigorous proof should probably proceed like this proof instead. $\endgroup$
    – John L.
    Mar 11 at 20:20
  • $\begingroup$ In what way did I not handle the case $P(s') = P(s^*)$ properly, since I consider $P(s') \leq P(s^*)$ and so also the case $P(s') = P(s^*)$? $\endgroup$
    – prcssngnr
    Mar 11 at 20:37
  • 2
    $\begingroup$ You wrote "So $OPT$ must contains $s^*$". Well, it is possible that $OPT$ does not contain $s^*$. For example, $n=2$, both exercises have $3$ points with deadline day $1$. Then for anyone of the two exercises, an optimal solution might not contain it. In general, there could be more than one optimal solution, although all of them will score the same amount of points. $\endgroup$
    – John L.
    Mar 11 at 20:46
  • 1
    $\begingroup$ I see what you mean, though still it holds that, always picking $s^*$ never leads to a suboptimal solution. I guess I could be more precise about this. $\endgroup$
    – prcssngnr
    Mar 11 at 21:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.