Trouvez des travaux planifiés sans chevauchement avec un coût maximum

Étant donné un ensemble de n travaux avec [heure de début, heure de fin, coût], trouvez un sous-ensemble de sorte qu'aucun travail ne se chevauche et que le coût soit maximum.

Maintenant, je ne sais pas si un algorithme gourmand fera l'affaire. C'est-à-dire, trier par coût et toujours prendre le prochain travail qui ne se recoupe pas et avec un coût maximum entre les deux.

Est-ce équivalent à un problème de sac à dos? Comment pourrais-je l'approcher?

Le graphique des travaux qui se chevauchent est un graphique d'intervalle . Les graphiques d'intervalle sont des graphiques parfaits. Donc, ce que vous essayez de faire, c'est de trouver un ensemble indépendant du poids maximum (c'est-à-dire qu'il n'y a pas deux chevauchements) dans un graphique parfait . Cela peut être résolu en temps polynomial. L'algorithme est donné dans "Algorithmes polynomiaux pour des graphes parfaits" , par M. Grötschel, L. Lovász et A. Schrijver.

Il existe un certain nombre de cas particuliers de graphes parfaits pour lesquels les gens ont découvert des algorithmes plus simples et plus efficaces pour cette tâche. Je ne sais pas si les graphiques d'intervalle entrent dans l'un de ces cas particuliers.

L'algorithme gourmand ne peut pas aider dans ce cas. Et cela ne pouvait pas être comparé à des problèmes fractionnels ou à 0-1. Le premier pourrait être résolu par un algorithme gourmand en O (n) et le second est NP.

Le problème que vous rencontrez pourrait être forcé par la force dans O (2 ^ n). Mais vous pouvez l'optimiser en utilisant une programmation dynamique.

1) Triez les intervalles par heure de début.

2) Initialiser int [] costs = new int [jobs.length] avec Integer.MIN_VALUE (ou toute valeur négative);

3) Définissez la routine récursive de suivi (voici Java):

private int findCost(Job[] jobs, int k, int[] costs) {
   if(k >= jobs.length) {
      return 0;
   }
   if(costs[k] < 0) {
     int x = findNextCompatibleJob(jobs, k);
     int sumK = jobs[k].cost + findCost(jobs, x, costs);
     int sumK1 = findCost(jobs, k + 1, costs);
     costs[k] = Math.max(sumK, sumK1);
   }
   return costs[k];
}

private int findNextCompatibleJob(Job[] jobs, int k) {
   int finish = jobs[k].finish;
   for(int i = k + 1; i < jobs.length; i++) {
     if(jobs[i].start > finish) {
        return i;
     }
   }
   return Integer.MAX_VALUE;
}

4) Commencez la récursivité avec k = 0;

J'ai implémenté uniquement une routine de récursivité alors que d'autres parties sont triviales. J'ai considéré que tout coût est> = 0. S'il peut y avoir des emplois à coût négatif, nous devons ajouter une vérification pour cela et simplement passer ces emplois sans considération.

On pourrait implémenter cela dans O (nlogn)

Pas:

1. Trier les intervalles en fonction de l'heure de fin
2. définir p (i) pour chaque intervalle, en donnant le plus grand point final qui est plus petit que le point de départ du i-ème intervalle. Utilisez la recherche binaire pour obtenir nlogn
3. définir d [i] = max (w (i) + d [p (i)], d [i-1]).

initialiser d [0] = 0

Le résultat sera en d [n] n- le nombre d'intervalles.

Complexité globale O (nlogn)

import java.util.*;
class Interval {
  public int start;
  public int end;
  public int cost;
  public Interval(int start, int end, int cost){
    this.start = start;
    this.end = end;
    this.cost = cost;
  }
}
public class BestCombinationFinder {
  public int getBestCombination(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) {
      return 0;
    }
    Collections.sort(intervals, new Comparator<Interval>() {
      public int compare(Interval i1, Interval i2) {
        if (i1.end < i2.end) {
          return -1;
        }
        else if (i1.end > i2.end) {
          return 1;
        }
        return 0;
      }
    });
    return findBestCombination(intervals);
  }
  private int findBestCombination(List<Interval> intervals) {
    int[] dp = new int[intervals.size() + 1];
    for (int i = 1; i <= intervals.size(); i++) {
      Interval currInt = intervals.get(i - 1);
      int pIndex = find(intervals, currInt.start, 0, intervals.size() - 1);
      dp[i] = Math.max(dp[pIndex+1] + currInt.cost, dp[i - 1]);
    }
    return dp[intervals.size()];
  }
  private int find(List<Interval> intervals, int target, int left, int right) {
    if (left > right) {
      return right;
    }
    else {
      int mid = (left + right) / 2;
      if (intervals.get(mid).end == target) {
        return mid;
      }
      else if (intervals.get(mid).end > target) {
        return find(intervals, target, left, mid - 1);
      }
      else {
        return find(intervals, target, mid + 1, right);
      }
    }
  }
}

Oui, cela équivaut à un problème de sac à dos. Tenez compte de l'heure de fin du travail et préparez la table comme un sac à dos. Avant de lire la solution suivante, veuillez vérifier le problème du sac à dos et sa solution.

// Input:
// Jobs (stored in array jobs)
// Number of jobs (n)

find the maximum end time from given n jobs => max_end

for j from 0 to max_end do
         table[0, j] := 0
end for 

for i from 1 to n do
    for j from 0 to max_end do
        if jobs[i].end <= j then
           table[i, j] := max(table[i-1, j], table[i-1, jobs[i].start] + jobs[i].cost)
       else
           table[i, j] := table[i-1, j]
       end if
    end for
 end for

Vous pouvez également imprimer les travaux planifiés en parcourant le tableau:

j := max_end;
for i from n to 1 do
    if table[i][j] != table[i-1][j]
        print jobs[i]
        j = jobs[i].start; 
    end if
end for

La complexité est la même que le problème du sac à dos.