Improving next_permutation algorithm

Question

I have the following homework:

We have N works, which durations are: t1, t2, ..., tN, which's deadlines are d1, d2, ..., dN. If the works aren't done till the deadline, a penalty is given accordingly b1, b2, ..., bN. In what order should the jobs be done, that the penalty would be minimum?

I've written this code so far and it's working but I want to improve it by skipping unnecessary permutations. For example, I know that the jobs in order: 1 2 3 4 5 - will give me 100 points of penalty and if I change the order let's say like this: 2 1 ..... - it gives me instantly 120 penalty and from this moment I know I don't have to check all of the rest permutations which start with 2 1, I have to skip them somehow. Here's the code:

int finalPenalty = -1;
bool z = true;
while(next_permutation(jobs.begin(), jobs.end(), compare) || z)
{
    int time = 0;
    int penalty = 0;
    z = false;
    for (int i = 0; i < verseNumber; i++)
    {
        if (penalty > finalPenalty && finalPenalty >= 0)
            break;
        time += jobs[i].duration;
        if (time > jobs[i].deadline)
            penalty += jobs[i].penalty;
    }
    if (finalPenalty < 0 || penalty < finalPenalty)
    {
        sortedJobs = jobs;
        finalPenalty = penalty;
    }
    if (finalPenalty == 0)
        break;
}

I think I should do this somewhere here:

if (penalty > finalPenalty && finalPenalty >= 0)
            break;

But I'm not sure how to do this. It skips me one permutation here if the penalty is already higher, but it doesn't skip everything and it still does next_permutation. Any ideas?

EDIT: I'm using vector and my job structure looks like this:

    struct job
    {
        int ID;
        int duration;
        int deadline;
        int penalty;
    };

ID is given automatically when reading from file and the rest is read from file (for example: ID = 1, duration = 5, deadline = 10, penalty = 10)

Answer 1

If you are planning to use next_permutation function provided by STL, there is not much you can do.

Say the last k digits are redundant to check. If you will use next_permutation function, a simple, yet inefficient strategy you can use is calling next_permutation for k! times(i.e. number of permutations of those last k elements) and just not go through with computing their penalties, as you know they will be higher. (k! assumes there are not repetitions. if you have repetitions, you would need to take extra measures to be able to compute that) This would cost you O(k!n) operations on the worst case, as next_permutation has linear time complexity.

Let's consider how we can improve this. A sound strategy may be, once an inefficient setting is found, before calling next_permutation again, ordering those k digits in descending order so that the next call would effectively skip the inefficient portion of permutations that need not be checked. Consider the following example.

Say our method found 1 2 3 4 5 has a penalty of 100. Then, while computing 2 1 3 4 5 at the next step, if our method finds that we got a penalty higher than 100 only after computing 2 1, if could just sort 3 4 5 in descending order using sort along with your custom comparison mechanism, and just skip the rest of the loop, arriving at another next_permutation call, which would give you 2 1 4 3 5, the next sequence to continue.

Let's consider how much skipping costs. This method requires sorting those k digits and calling next_permutation, which has an overall time complexity of O(klogk + n). This is a huge improvement over the previous method which has O(k!n).

See below for an crude implementation of the method I propose as an improvement over your existing code. I had to use type auto as you did not provide the exact type for jobs. I also sorted then reversed those k digits, as you did not provide your comparison function and I wanted to emphasize that what I was doing was reversing the ascending order.

int finalPenalty = -1;
bool z = true;
while(next_permutation(jobs.begin(), jobs.end(), compare) || z)
{
    int time = 0;
    int penalty = 0;
    z = false;
    auto it = jobs.begin();
    for (int i = 0; i < verseNumber; i++)
    {
        time += jobs[i].duration;
        if (time > jobs[i].deadline)
        {
            penalty += jobs[i].penalty;
            if(finalPenalty >= 0 && penalty > finalPenalty)
            {
                it++; // only the remaining jobs need to be sorted in reverse
                sort(it, jobs.end(), compare);
                reverse(it, jobs.end());
                break;
            }
        }
        it++;
    }
    if (finalPenalty < 0 || penalty < finalPenalty)
    {
        sortedJobs = jobs;
        finalPenalty = penalty;
    }
    if (finalPenalty == 0)
        break;
}