Thuật toán tham lam

Thuật toán tham lam(Greedy Algorithm)

1. Định nghĩa
   
   1. là thuật toán xem xét quá trình giải quyết bài toán bằng việc tạo nên lựa chọn tối ưu cục bộ tại mỗi bước thực hiện với mong muốn tìm ra lựa chọn tối ưu toàn cục
   2. Chính vì thế mà kết quả thu được cuối cùng có thể không tối ưu nhất cho bài toán mà chỉ là một nghiệm có thể chấp nhận được với thời gian tương đối ngắn
2. Thành phần
   gồm 5 thành phần chính
   1. Một tập các ứng viên mà giải pháp thực hiện tạo ra.
   2. Một hàm lựa chọn (selection fuction) để chọn ứng viên tốt nhất cho giải pháp
   3. Một hàm thực thi (feasibility function) được sử dụng để xác định các ứng viên có thể có đóng góp cho giải pháp thực thi.
   4. Một hàm mục tiêu (objective function) dùng để xác định giá trị của phương pháp hoặc một phần của giải pháp
   5. Một hàm giải pháp (solution function) dùng để xác định khi nào giải pháp kết thúc
3. Ví dụ
   1. Lớp bài toán chi phí: Bài toán cái túi
      Input:
      1. remain: sức chứa của túi có thể chứa
      2. w[] : tập các giá trị của từng đồ vật
      3. p[] : tập khối lượng tương ứng của từng đồ vật
      
      Output: Giá trị tối đa có thể chứa trong túi đó
      Nguyên tắc: chọn những vật có pi/wi cao nhất đồng thời sức chứa của túi có thể chứa được vật đó (remain > wi) mỗi khi cho thêm vật vào túi ta cũng giảm sức chứa của túi đi.

          int proc(int W, int N) { 
              bubble_sort(p, w, N); // sort theo ty le p[i]/w[i]
                      
              int remain = W;  
              int res = 0.0; 
                      
              for (int i = 0; i < n; i++) { 
                  if (w[i] <= remain) { 
                      remain -= w[i]; 
                      res += p[i]; 
                  }
              } 
              return res; 
          }
                      

   2. Lớp bài toán sắp xếp: Bài toán sắp xếp công việc
      Input:
      1. n: Số lượng công việc
      2. S[] : Thời gian bắt đầu của từng công việc
      3. E[] : Thời gian kết thúc của từng công việc tương ứng
      
      Output: Số công việc có thể làm tối đa, và thứ tự của các công việc đó
      Nguyên tắc: Sắp xếp các công việc tăng dần theo thời gian kết thúc. Chọn hd đc xếp đầu tiên sau đó chọn các hd có giờ bắt đầu lớn hơn giờ kết thúc của hd trước đó
      

          void qsort(int a[], int start, int end)
          {
              // quicksort theo thời gian kết thúc
              if (start >= end)
                  return;
              int index = rand() % (start-end) + start;
              int pivot = a[index];
              int k = start - 1;
              swap(index, end);
              for (int i = start; i < end; i++)
              if (a[i] < pivot)
              {
                  k++;
                  swap(i, k);
              }
              k++;
              swap(k, end);
              qsort(a, start, k-1);
              qsort(a, k+1, end);
          }
      
          void proc()
          {
              qsort(a,0,n-1); // sx theo thời gian kết thúc
              // xử lí
              int res = 1;
              int end = e[0];
              for (int i = 1; i < N; i++)
              {
                  if (e[i] == end)
                      continue;
                  if (s[i] >= end)
                  {
                      res++;
                      end = e[i];
                  }
              }
              printf("%dn", res);
          }