Temukan pekerjaan terjadwal yang tidak tumpang tindih dengan biaya maksimum

Diberikan satu set n pekerjaan dengan [waktu mulai, waktu selesai, biaya] menemukan subset sehingga tidak ada 2 pekerjaan yang tumpang tindih dan biaya maksimum.

Sekarang saya tidak yakin apakah algoritma serakah akan melakukan trik. Yaitu, urutkan berdasarkan biaya dan selalu mengambil pekerjaan berikutnya yang tidak bersinggungan dan dengan biaya maksimum antara keduanya.

Apakah ini setara dengan masalah ransel? Bagaimana saya bisa mendekatinya?

Grafik pekerjaan yang tumpang tindih adalah grafik interval . Grafik interval adalah grafik sempurna. Jadi apa yang Anda coba lakukan adalah menemukan set independen berat maksimum (yaitu, tidak ada dua tumpang tindih) dalam grafik yang sempurna . Ini dapat diselesaikan dalam waktu polinomial. Algoritma ini diberikan dalam "Algoritma Polinomial untuk Grafik Sempurna" , oleh M. Grötschel, L. Lovász, dan A. Schrijver.

Ada sejumlah kasus khusus dari grafik sempurna dimana orang telah menemukan algoritma yang lebih sederhana dan lebih efisien untuk tugas ini. Saya tidak tahu apakah grafik interval termasuk dalam salah satu kasus khusus ini.

Algoritma serakah tidak dapat membantu dalam kasus itu. Dan itu tidak bisa dibandingkan dengan masalah fraksional atau 0-1. Yang pertama bisa diselesaikan dengan algoritma serakah di O (n) dan yang kedua adalah NP.

Masalah yang Anda miliki bisa menjadi kasar di O (2 ^ n). Tetapi Anda bisa mengoptimalkannya menggunakan pemrograman dinamis.

1) Urutkan interval dengan waktu mulai.

2) Inisialisasi int [] biaya = int baru [jobs.length] dengan Integer.MIN_VALUE (atau nilai negatif apa pun);

3) Tentukan mengikuti rutin rekursif (di sini adalah 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) Mulai rekursi dengan k = 0;

Saya hanya menerapkan rutin rekursi sementara bagian lainnya sepele. Saya menganggap bahwa biaya apa pun>> 0. Jika mungkin ada pekerjaan dengan biaya negatif, kita perlu menambahkan cek untuk itu dan hanya meneruskan pekerjaan itu tanpa pertimbangan.

Seseorang dapat mengimplementasikan ini di O (nlogn)

Langkah:

1. Sortir interval berdasarkan waktu akhir
2. tentukan p (i) untuk setiap interval, memberikan titik akhir terbesar yang lebih kecil dari titik awal interval ke-i. Gunakan pencarian biner untuk mendapatkan nlogn
3. define d [i] = max (w (i) + d [p (i)], d [i-1]).

inisialisasi d [0] = 0

Hasilnya akan menjadi d [n] n- jumlah interval.

Kompleksitas keseluruhan 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);
      }
    }
  }
}

Ya, itu setara dengan masalah ransel. Pertimbangkan waktu akhir pekerjaan dan persiapkan meja seperti ransel. Sebelum membaca solusi berikut, silakan periksa masalah knapsack dan solusinya.

// 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

Anda juga dapat mencetak pekerjaan yang dijadwalkan dengan melintasi tabel:

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

Kompleksitas sama dengan masalah ransel.