Algorytm wyboru zajęć

0

Mamy następujący problem:

Problem wyboru zajęć: dany jest zbiór n zajęć, każe z nich ma czas rozpoczęcia i czas zakończenia.
Dysponujesz jedną salą wykładową, w której przez określoną ilość godzin w ciągu dnia mogą się
odbywać zajęcia. W danej chwili w sali mogą się odbywać tylko jedne zajęcia. Jeśli jedne zajęcia
kończą się w czasie t, to kolejne mogą się zaczynać w czasie t. Zaproponuj algorytm, który
wybierze zajęcia w taki sposób, aby ich łączny czas trwania był możliwie najdłuższy.

Plik wejściowy:
Kolejne linie: czas rozpoczęcia i zakończenia poszczególnych zajęć
0 3
1 3
2 4
2 5
4 8
6 8
7 10
8 10
0 2
1 2

Plik wyjściowy:
Pierwsza linia: łączna ilość godzin wybranych zajęć.
Kolejne linie: czas rozpoczęcia i zakończenia wybranych zajęć
Ostatnia linia: ilość operacji elementarnych, które się wykonały podczas działania programu
10
0 2
2 4
4 8
8 10
10

Mój algorytm:

/*
 Problem wyboru zajęć: dany jest zbiór n zajęć, każe z nich ma czas rozpoczęcia i czas zakończenia.
 Dysponujesz jedną salą wykładową, w której przez określoną ilość godzin w ciągu dnia mogą się 
 odbywać zajęcia. W danej chwili w sali mogą się odbywać tylko jedne zajęcia. Jeśli jedne zajęcia 
 kończą się w czasie t, to kolejne mogą się zaczynać w czasie t. Zaproponuj algorytm, który 
 wybierze zajęcia w taki sposób, aby ich łączny czas trwania był możliwie najdłuższy.

 Plik wejściowy: 
 Kolejne linie: czas rozpoczęcia i zakończenia poszczególnych zajęć

 Plik wyjściowy:
 Pierwsza linia: łączna ilość godzin wybranych zajęć.
 Kolejne linie: czas rozpoczęcia i zakończenia wybranych zajęć
 Ostatnia linia: ilość operacji elementarnych, które się wykonały podczas działania programu

 Przykład:
 Plik wejściowy: 
 0 3
 1 3
 2 4
 2 5
 4 8
 6 8
 7 10
 8 10
 0 2
 1 2

 Plik wyjściowy:
 10
 0 2
 2 4
 4 8
 8 10
 10

REF:
http://www.cs.put.poznan.pl/arybarczyk/ProgrDynamiczne.pdf
 */
package asd_4_2;
 
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;
 
/**
 * @author GrzegorzOginski at gmail dot com
 */
public class Asd_4_2 {
 
    static class Hour implements Comparable<Hour> {
 
        private static int count;
        private final Integer startHour;
        private final Integer endHour;
        private final int obiectId;
 
        Hour(final int s, final int e) {
            startHour = s;
            endHour = e;
            count++;
            obiectId = count;
        }
 
        @Override
        public int compareTo(Hour h) {
            return this.endHour.compareTo(h.endHour);
        }
 
        @Override
        public String toString() {
            return Integer.toString(this.startHour + this.endHour);
        }
 
    }
 
    static class CompareByEnd implements Comparator<Hour> {
 
        @Override
        public int compare(Hour h1, Hour h2) {
            return h1.endHour < h2.endHour ? -1 : Objects.equals(h1.endHour, h2.endHour) ? 0 : 1;
        }
    }
 
    static class CompareByStart implements Comparator<Hour> {
 
        @Override
        public int compare(Hour h1, Hour h2) {
            return h1.startHour < h2.startHour ? -1 : Objects.equals(h1.startHour, h2.startHour) ? 0 : 1;
        }
    }
 
        //weź liste
        //dodaj pierwsze zajecia do zbioru (najszybciej sie konczące)
        //dla wszystkich zajec
            //sprawdż czy czas zakoczenia nastepnego zajecia nie naklada sie na zajecia juz dodane
            //jesli nie to dodaj do zbioru wyjsciowego
             //jestli tak to pomin
        //zwroc zbior
    
    public static int elemOpsCount = 0;                     //licznik operacji elementarnych
    static List<Hour> selectHour2(List<Hour>h){
       
        List<Hour> selectedHours = new LinkedList<>();      //Lista zajec posortowana po end
        selectedHours.add(h.get(0));                        //Dodanie pierwszych zajęć jako najbardziej optymalnych (najwcześniej się kończą)
        for(int i = 1, j=i-1; i < h.size(); ++i)            //iterujemy po liscie od 1 do h.size()
        {
            elemOpsCount++;                                 //zliczanie operacji elementarnych
            if(h.get(j).endHour <= h.get(i).startHour)      //if czas zakończenia aktualnych zajec <= zajeciąm prze które iterujemy
            {   
                selectedHours.add(h.get(i));                //dodajemy te zajecia do listy
                j = i;                                      //aktualne zajecia wskazują teraz na iteratora
            }            
        }
       return selectedHours;                                //zwróc Liste zajec najlepiej wykorzystujacej zasób sali
    }
   
    //returens id of object
    static Integer[] selectHour(List<Hour> h) {
        Integer[] selectedHours = new Integer[h.size()];
        selectedHours[0] = h.get(0).obiectId; //set first
        for (int i = 1, j = i-1; i < h.size(); i++) {
            if (h.get(j).endHour <= h.get(i).startHour) {
                selectedHours[i] = h.get(i).obiectId;
                j = i;
            }
        }
        return selectedHours;
 
    }
 
    /**
     * @param args the command line arguments
     * @exception java.io.FileNotFoundException
     */
    public static void main(String[] args) throws FileNotFoundException, IOException {
        final String inputFile = "src/4_2_in";
        final String outputFile = "src/4_2_out";
        List<Hour> hours = new LinkedList<>();
        Scanner scanner = new Scanner(new File(inputFile));
        while (scanner.hasNext()) {
            hours.add(new Hour(scanner.nextInt(), scanner.nextInt()));
        }
        
        //sort hours
        Collections.sort(hours, new CompareByEnd()); //sort by end of hour range
 
        //check if works, compute some 
        List<Hour> hours2 = selectHour2(hours);
        int sum = 0;
        for(Hour h: hours2){
            sum += (h.endHour-h.startHour);
            System.out.println(h.startHour+" "+h.endHour);
        }
        
        //save output file
        File outFile = new File(outputFile);
        try(PrintWriter printWriter = new PrintWriter(outFile)){
            printWriter.println(sum);
            for(Hour h: hours2){
                printWriter.println(h.startHour+" "+h.endHour);
            }
            printWriter.println(elemOpsCount);
        }
        
    }
}

Napisałem algorytm który dla podanych wejściowych zwraca poprawne wyniki, ale prowadzący podał mi dane wejściowe które dają nie takie wyniki jak by oczekiwał. Otóz dla danych jak niżej mój algorytm zwraca wynik nieoptymalny (02 35 68 zamiast 03 35 68)

0 2
0 3
3 5
6 8

Jak naprawić ten algorytm by zawsze był wynik optymalny? Proszę o wskazówki.

0

Magister Katarzyna będzie wiedziała...

0

Rozwiązałem problem. Podpowiedź dla potomnych: Zajęcia optymalne do dodania jako pierwsze to nie tylko zajęcia które się najszybciej kończą, ale też trawją jak najdłużej. Do zamknięcia.

0

ale w przypadku np
0 1
0 5
1 7
7 9
9 10

to nie zadziała, bo weźmiesz wtedy 0 5, 7 9, 9 10, a powinieneś wziąć 0 1, 1 7, 7 9, 9 10.

0

Masz rację, udało się rozwiązać stosując programowanie dynamiczne. Rozwiązanie poniżej.

  static List<Hour> selectHourDP(List<Hour> h){
        final int n = h.size()-1;                                               //number of list elements
        
        //compute first not overlapping on the left and save in class field
        int[] firstNotOverlapp = new int[n + 1];                                //first Index Of Not Overlapping On The Right
        for (int i = n; i > 0; i--) {                                           //from end to begining...
            for (int j = i - 1; j > 0; j--) {                                   //...check with all elements on the left
                elemOpsCount++;                                                 //count elementary operations
                if (!isOverlapping(h.get(i), h.get(j))) {                       //if is not overlapping with element...
                    h.get(i).firstIndexOfNotOverlappingOnTheLeft = j;            //...mark this elements as fist not overlapping on the left
                    firstNotOverlapp[i] = j;                                    // -/- implementation in array
                    break;                                                      //if found break and check for next element
                }
            }
        }
        
        //compute optimal solution using dynamic programming
        int[] memory = new int[n + 1];                                          //array for storing optimal solution
        memory[0] = 0;                                                          //zero index must by zero
        for (int k = 1; k <= n; k++) { //O(n)                                   //from first index to size of list
            //memory[k] = Math.max(h.get(k).length + memory[h.get(k).firstIndexOfNotOverlappingOnTheRight], memory[k-1]); //na liście
            memory[k] = Math.max(h.get(k).length + memory[firstNotOverlapp[k]], memory[k - 1]); //store max (optimal) value from two elements
        }
        //err.println("memory[] " + Arrays.toString(memory));                   //DEBUG

        //build and return output list TODO
        memory[0] = 0;                                                          
        int[] pred = new int[n + 1];
        //compute solution in addition to its values
        for (int j = 1; j <= n; j++) {
            elemOpsCount++;
            if (((h.get(j).length) + memory[h.get(j).firstIndexOfNotOverlappingOnTheLeft]) > memory[j - 1]) {
                memory[j] = h.get(j).length + memory[h.get(j).firstIndexOfNotOverlappingOnTheLeft];
                pred[j] = h.get(j).firstIndexOfNotOverlappingOnTheLeft;
            } else {
                memory[j] = memory[j - 1];
                pred[j] = j - 1;
            }
        }
        //err.println("memory[] " + Arrays.toString(memory));                   //DEBUG
        //err.println(("pred[] " + Arrays.toString(pred)));                     //DEBUG

        //find solutions in class
        List<Hour> outList = new ArrayList<>();
        int j = n;
        while (j > 0) {
            elemOpsCount++;
            if (pred[j] == h.get(j).firstIndexOfNotOverlappingOnTheLeft) {
                outList.add(h.get(j));
            }
            j = pred[j];
        }
        return outList; //TODO Compute elemetary operations
    }
0

Podany przez Ciebie na górze algorytm (odniesienie na samej górze do pliku pdf) maksymalizuje liczbę zajęć, a nie sumaryczną długość ich trwania.
Zobacz na to: en.wikipedia.org/wiki/Activity_selection_problem#Weighted_Activity_Selection_Problem
jako wagę ustalasz długość przedziału (czyli czas trwania zajęć) i już.

1 użytkowników online, w tym zalogowanych: 0, gości: 1