Максимизируйте прибыль, Расписание работы

Question

У меня есть сценарий, в котором каждый временной интервал имеет прибыль и многословие на выбор. Мне нужно выбрать задания в каждом временном интервале, чтобы получить максимальную максимальную прибыль. Мне нужна максимальная полученная прибыль и график.

Единственное, что я могу придумать, это попытаться для каждого comibnation, используя bruteforce. Как я могу эффективно решить эту проблему. Есть ли способ сделать это лучше, используя конкретный алгоритм или структуру данных?

В приведенном ниже примере любое задание J1, J2, J4 может быть выбрано для временного интервала 1. Аналогично для других временных интервалов может быть выбрано любое или любое из заданий. Только одно задание может быть выбрано для определенного временного интервала. Если задание выполняется в один временной интервал, это невозможно сделать снова.

Например. Если j1 делается в TS1, он не может быть выбран снова в TS2

+----------+--------+----------------------+ 
| TimeSlot | Profit | Possible Job   | 
+----------+--------+----------------------+ 
|  1 |  50 | J1 or J2 or J4  | 
|  2 | 100 | J1     | 
|  3 |  20 | J2     | 
|  4 |  60 | J5 or J4    | 
|  5 |  15 | J1 or J2 or J3 or J6 | 
+----------+--------+----------------------+ 

Answer 1

Это может быть решена оптимально weighted maximum matching in bipartite graph.

В здесь, ваш граф G=(U,V,E), где:

U = {1, 2, ...., n} // time slots 
V = {J1, J2, ..., J_m} // jobs 
E = { (i,J) | if job J can be done in time i } 
w(i,J) = profit(i) 

maxmum соответствия в приведенном выше графике переводится непосредственно к оптимальному решению, выполняя задачу J во временном интервале i тогда и только тогда максимального соответствия соответствует узлу J с узлом i.

Answer 2

общественного класса JobProfitMaximizer {

private int numberOfJobs; 
private Job[] jobs; 
private int maxProfit; 

public class JobComparator implements Comparator<Job> { 

    @Override 
    public int compare(Job arg0, Job arg1) { 
     if (arg0.end <= arg1.end) 
      return -1; 
     else 
      return 1; 
    } 
} 

public JobProfitMaximizer() { 
    numberOfJobs = 0; 
    maxProfit = 0; 
} 

private void printJobProfiles() { 
    for (Job j : jobs) { 
     System.out.println(j.start + " " + j.end + " " + j.profit); 
    } 
} 

private void createJobProfiles() { 
    jobs = new Job[numberOfJobs]; 
    File inputFile = new File("***Filepath***********"); 
    Scanner sc = null; 
    int jobCounter = 0; 
    try { 
     sc = new Scanner(inputFile); 
     while (sc.hasNextLine()) { 
      String s = sc.nextLine(); 
      String[] profileOfJob = s.split(" "); 
      int start = Integer.parseInt(profileOfJob[1]); 
      int end = Integer.parseInt(profileOfJob[2]); 
      int profit = Integer.parseInt(profileOfJob[3]); 
      jobs[jobCounter] = new Job(start, end, profit); 
      jobCounter = jobCounter + 1; 
     } 
    } catch (FileNotFoundException e) { 
     System.out.println("The file is not present"); 
    } finally { 
     try { 
      if (sc != null) 
       sc.close(); 
     } catch (Exception f) { 
      System.out.println(f.getMessage()); 
     } 
    } 
} 

private void setNumberOfJobs() { 
    File inputFile = new File("***Filepath***********"); 
    Scanner sc = null; 
    int countOfJobs = 0; 
    try { 
     sc = new Scanner(inputFile); 
     while (sc.hasNextLine()) { 
      countOfJobs = countOfJobs + 1; 
      sc.nextLine(); 
     } 
     numberOfJobs = countOfJobs; 
     System.out.println(numberOfJobs); 
    } catch (FileNotFoundException e) { 
     System.out.println("The file is not present"); 
    } finally { 
     try { 
      if (sc != null) 
       sc.close(); 
     } catch (Exception f) { 
      System.out.println(f.getMessage()); 
     } 
    } 
} 

private void sortJobsOnFinishTimes() { 
    JobComparator jc = new JobComparator(); 
    Arrays.sort(jobs, jc); 
} 

private void calculateMaximumProfit() { 
    int[] T = new int[numberOfJobs]; 
    T[0] = jobs[0].profit; 

    for (int i = 1; i < numberOfJobs; i++) { 
     T[i] = Math.max(T[i - 1], jobs[i].profit); 
     for (int j = i - 1; j >= 0; j--) { 
      if (jobs[j].end <= jobs[i].start) { 
       T[i] = Math.max(T[i], T[j] + jobs[i].profit); 
       break; 
      } 
     } 
    } 

    int currentMaxProfitValue = T[0]; 

    for (int m : T) { 
     if (m > currentMaxProfitValue) { 
      currentMaxProfitValue = m; 
     } 
    } 
    maxProfit = currentMaxProfitValue; 
} 

public static void main(String args[]) { 
    JobProfitMaximizer j = new JobProfitMaximizer(); 
    j.setNumberOfJobs(); 
    j.createJobProfiles(); 
    j.sortJobsOnFinishTimes(); 
    j.calculateMaximumProfit(); 
    System.out.println("The maximum profit is " + j.maxProfit); 
} 

}