ASD e 02 2005 7

Egzamin ASD

Studia dzienne, 7go lutego 2005

Nazwisko

Nr studenta............Nr grupy

Zadanie 7 (lOpunktów) Programowanie dynamiczne

Pewna firma oferuje n nowych miejsc pracy ponumerowanych od 1 do n. Zgłosiło się k kandydatów, którym przypisano numery od 1 do k, k<n, ze względu na kolejność zgłoszenia. Każdy ze zgłaszających się może zostać zatrudniony na dowolnym z oferowanych stanowisk, z tym, że osoba zgłaszająca się później może zająć tylko stanowisko o numerze większym niż osoba, która zgłosiła się wcześniej. Specjalna komisja ocenia przydatność każdego z kandydatów na dowolne ze stanowisk. Zadanie polega na wybraniu stanowisk dla wszystkich k kandydatów w taki sposób, by suma ich ocen była największa (Rozwiązanie optymalne z punktu widzenia firmy!).

Dane :

n - liczba stanowisk pracy, k - liczba kandydatów,

Tab(k x n) - tablica ocen; w wierszu o numerze i zapisane jest n liczb całkowitych będących ocenami przydatności itego kandydata na stanowiska od 1 do n.

Polecenia:

1.    Zapisz równanie rekurencyjne charakteryzujące optymalne rozwiązanie problemu OPT(n,k).

2.    Zaproponuj szkic algorytmu, który znajduje optymalne przypisanie kandydatów do stanowisk. Opisz metodę postępowania i użytą strukturę danych.

3.    Uzasadnij, że algorytm rekurencyjny jest istotnie gorszy od zaproponowanego przez Ciebie rozwiązania.