Verbesserung next_permutation Algorithmus

Question

Ich habe folgende Hausaufgaben:

Wir haben N arbeitet, die Laufzeiten sind: T1, T2, ..., tN, die Fristen ist d1, d2, ..., dN. Wenn die Arbeiten nicht bis zum Stichtag erledigt sind, wird eine Strafe entsprechend b1, b2, ..., bN gegeben. In welcher Reihenfolge sollten die Jobs erledigt werden, dass die Strafe minimal wäre?

Ich habe diesen Code bisher geschrieben und es funktioniert, aber ich möchte es verbessern, indem Sie unnötige Permutationen überspringen. Zum Beispiel weiß ich, dass die Aufträge in Reihenfolge: 1 2 3 4 5 - geben Sie mir 100 Punkte Strafe und wenn ich die Reihenfolge ändern sagen wir so: 2 1 ..... - es gibt mir sofort 120 Strafe und von diesem Moment an weiß ich, dass ich nicht alle Restpermutationen überprüfen muss, die mit 2 1 beginnen, ich muss sie irgendwie überspringen. Hier ist der 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; 
} 

Ich glaube, ich sollte hier das irgendwo tun:

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

Aber ich bin nicht sicher, wie dies zu tun. Es überspringt mich hier eine Permutation, wenn die Strafe schon höher ist, aber es überspringt nicht alles und es macht noch next_permutation. Irgendwelche Ideen?

EDIT: Ich bin mit Vektor und mein Job Struktur sieht wie folgt aus:

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

ID automatisch gegeben, wenn aus der Datei und der Rest Lesen aus Datei (zum Beispiel lauten: ID = 1, Dauer = 5, Deadline = 10, Penalty = 10)

Answer 1

Wenn Sie die Funktion next_permutation von STL verwenden möchten, können Sie nicht viel tun.

Sagen Sie, die letzten k Ziffern sind redundant zu überprüfen. Wenn Sie die Funktion next_permutation verwenden, können Sie eine einfache, aber ineffiziente Strategie verwenden, indem Sie next_permutation für k aufrufen! Zeiten (d. h. Anzahl der Permutationen dieser letzten k Elemente) und einfach nicht mit der Berechnung ihrer Strafen, wie Sie wissen, dass sie höher sein werden. (k! nimmt an, dass es keine Wiederholungen gibt. Wenn Sie Wiederholungen haben, müssten Sie zusätzliche Maßnahmen ergreifen, um dies berechnen zu können) Dies würde Sie O (k! n) Operationen im schlimmsten Fall kosten, wie next_permutation has linear time complexity.

Lassen Sie uns überlegen, wie wir das verbessern können. Eine Tonstrategie kann sein, dass, sobald eine ineffiziente Einstellung gefunden ist, vor dem erneuten Aufruf von next_permutation diese k Ziffern in absteigender Reihenfolge angeordnet werden, so dass der nächste Aufruf den ineffizienten Teil der Permutationen, die nicht überprüft werden müssen, überspringt. Betrachten Sie das folgende Beispiel.

Sagen Sie unsere Methode gefunden 1 2 3 4 5 hat eine Strafe von 100. Dann, während Berechnung 2 1 3 4 5 im nächsten Schritt, wenn unsere Methode findet, dass wir eine Strafe höher als 100 erst nach Berechnung 2 1 , wenn Sie einfach 3 4 5 in absteigender Reihenfolge unter Verwendung von sort zusammen mit Ihrem benutzerdefinierten Vergleichsmechanismus sortieren könnten, und einfach den Rest der Schleife überspringen und zu einem nächsten next_permutation-Aufruf kommen, der Ihnen 2 1 4 3 5, die nächste Sequenz zum Fortfahren geben würde .

Lassen Sie uns betrachten, wie viel Kosten überspringt. Dieses Verfahren erfordert das Sortieren dieser k Ziffern und das Aufrufen von next_permutation, was eine Gesamtkomplexität der Zeit von O (klogk + n) hat. Dies ist eine große Verbesserung gegenüber dem vorherigen Verfahren, das O (k! N) hat.

Siehe unten für eine grobe Implementierung der Methode, die ich als eine Verbesserung gegenüber Ihrem vorhandenen Code vorschlagen. Ich musste Typ auto verwenden, da Sie den genauen Typ für Jobs nicht angegeben haben. Ich sortierte auch reversed diese k Ziffern, da Sie Ihre Vergleichsfunktion nicht zur Verfügung stellten, und ich wollte betonen, dass das, was ich tat, war, die aufsteigende Reihenfolge umzukehren.

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; 
}