Мой вопрос связан с этим другим обсуждением.
Я пытаюсь реализовать этот алгоритм, используя динамическую программу в рекурсивном вызове.
Постановка задачи:
Задание j начинается с sj, заканчивается в fj и имеет вес или значение vj.
Две работы совместимы, если они не пересекаются.
Цель: найти подмножество взаимно совместимых работ с максимальным весом.
Решение, предлагаемое книгами, состоит в том, чтобы использовать таблицу решений для хранения всех суперпроблем, которые будут повторно использоваться при необходимости во время рекурсивного или итеративного вызова.
Шаги для решения проблемы:
Input: n, s1,...,sn , f1,...,fn , v1,...,vn
Sort jobs by finish times so that f1 > f2 >... > fn.
Compute p(1), p(2), ..., p(n)
Where p(j) = largest index i < j such that job i is compatible with j.
for j = 1 to n
M[j] = empty <-- solution table
M[j] = 0
M-Compute-Opt(j) {
if (M[j] is empty)
M[j] = max(wj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1))
return M[j]
}
А это мой код (соответствующие части):
глобальные вары:
typedef struct {
long start, stop, weight;
} job;
/* job array */
job *jobs;
/* solutions table */
long *solutions;
/* P(j) */
long *P;
-Сортируйте задания по времени окончания так, чтобы f1> f2> ...> fn
int compare(const void * a, const void * b) {
const job *ad = (job *) a;
const job *bd = (job *) b;
return (ad->stop - bd->stop);
}
//Jobs is filled above by parsing a datafile
qsort(jobs, njobs, sizeof(job), compare);
Вычислить p (1), p (2), ..., p (n), где p (j) = наибольший индекс i ‹j, такой, что задание i совместимо с j.
/*bsearch for finding P(J) */
int jobsearch(int start, int high){
if (high == -1) return -1;
int low = 0;
int best = -1;
int mid;
int finish;
while (low <= high){
mid = (low + high) /2 ;
finish = jobs[mid].stop;
if (finish >= start){
high = mid-1;
}else{
best = mid;
low = mid + 1;
}
}
return best;
}
int best;
for (i = 0; i < njobs; i++){
solutions[i] = -1l; //solutions table is initialized as -1
best = jobsearch(jobs[i].start,i-1);
if (best != -1)
P[i] = best;
else
P[i] = 0;
}
M-Compute-Opt (j):
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
/**
* The recursive function with the dynamic programming reduction
*/
long computeOpt(long j) {
if (j == 0)
return 0;
if (solutions[j] != -1l) {
return solutions[j];
}
solutions[j] = MAX(jobs[j].weight + computeOpt(P[j]), computeOpt(j - 1));
return solutions[j];
}
long res = computeOpt(njobs-1);
printf("%ld\n", res);
Я запускаю свою программу в нескольких тестовых примерах с большими данными (от 10k до 1m случайно сгенерированных заданий), сравнивая свой результат с ожидаемым результатом. В некоторых случаях это не удается. Иногда мой результат на e немного больше, а иногда немного меньше, чем ожидаемый результат. Я явно чего-то упускаю. Обратите внимание, что в большинстве случаев мой вывод верен, поэтому я думаю, что есть некоторые особые условия, с которыми я не могу справиться должным образом.
Не могу понять, в чем проблема.
Любая помощь приветствуется
ОБНОВЛЕНИЕ: я изменил рекурсивную функцию на итеративную, и теперь результат верен для всего тестового файла. Опять же, я не могу понять, почему рекурсивный не работает
