對很多最優化問題來說，采用動態規劃方法來解決就有點大材小用了。有時候我們可以采用貪心算法來取代。貪心算 法是通過所做的局部最佳選擇來產生一個全局最優解。而且和動態規劃不同的是，它是通過自頂向下的方式來解決每 一個子問題。而活動安排問題可以說是貪心算法的一個入門學習。 當我看到這個問題時，首先就想到了自己大一做ACM時在杭電acm裡遇到的一個題目：今年暑假不AC。可以說這個題 目就是活動安排問題的翻版，只是一個講的是怎麼安排最多活動，一個講的是最多能看到的電視節目。但本質是一樣 的。下面我就以今年暑假不AC這道題目來說明吧。 當時看到這道題的時候想的是排序，然後暴力找。開始是按開始時間排序的，結果發現這樣做沒什麼意義。因為有的 節目開始很早，但可能是最晚一個接受的，這樣的話不能保證能得出最大值。於是便以結束時間來排序，毫無疑問， 排在最前面的那個肯定可以看，然後以這個為基礎，從後依次遍歷，找到第一個開始時間大於這個結束時間的節目， 並將這個節目在數組中的下標i做一個標記，並設k = i，然後從這個節目開始繼續往後遍歷，找出第一個節目j，使 a[j].start >= a[k].end。然後設k = j，繼續往後遍歷。依此循環下去，直到遍歷完所有節目。實現代碼如下： [cpp] #include<stdio.h> struct Node { int s; int e; }; int main() { int n; int i, j, k; int count; Node a[100], temp; while (scanf("%d", &n), n) { for (i = 0; i < n; i++) { scanf("%d%d", &a[i].s, &a[i].e); } for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { if (a[j].e > a[j + 1].e) { temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } count = 1; k = 0; for (i = 1; i < n; i++) { if (a[i].s >= a[k].e) { k = i; //標記選中的節目 count++; } } printf("%d\n", count); } return 0; } 今天看了書才知道這用到了貪心思想，下面這個代碼是根據書上提供的遞歸形式寫的，意思是一樣的。 [cpp] #include<stdio.h> struct Node { int s; int e; }; int count; void fun (Node a[], int i, int n) { int m = i + 1; while ((m <= n) && (a[i].e > a[m].s)) m++; if (m <= n) { count++; fun (a, m, n); } } int main() { int n; int i, j; Node a[100], temp; while (scanf("%d", &n), n) { for (i = 0; i < n; i++) { scanf("%d%d", &a[i].s, &a[i].e); } for (i = 0; i < n - 1; i++) { for (j = 0; j < n - i - 1; j++) { if (a[j].e > a[j + 1].e) { www.2cto.com temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } count = 1; fun(a, 0, n-1); printf("%d\n", count); } return 0; }
