Content deleted Content added
→Weighted: format code |
|||
Line 43:
<syntaxhighlight line="1" lang="c">
// The vectors are already sorted from earliest to latest finish time.
int v[numOfVectors + 1]; // list of interval vectors
int w[numOfVectors + 1]; // w[j] is the weight for v[j].
int p[numOfVectors + 1]; // p[j] is the # of vectors that end before v[j] begins.
int M[numOfVectors + 1];
int finalSchedule[];
// v[0] does not exist. The first interval vector is set to v[1].
w[0] = 0; p[0] = 0; M[0] = 0;
for (int i = 1; i < numOfVector + 1; i++) {
M[i] = max(w[i] + M[p[i]], M[i - 1]);
}
// The maximum weight of the schedule is equal to M[numOfVectors + 1].
schedule (j) {
if (j == 0) { return; }
else if (w[j] + M[p[j]] >= M[j - 1]){
prepend(v[j], finalSchedule); // prepends v[j] to schedule.
schedule(p[j]);
} else { schedule(j - 1); }
}
</syntaxhighlight><ref>{{Cite book |last=Kleinberg |first=Jon |title=Algorithm Design |last2=Tardos |first2=Eva |publisher=Pearson |year=2006 |isbn=9780321295354 |edition=1st |pages=254}}</ref>
|