Thuật toán quy hoạch động

Thuật toán quy hoạch động(Dynamic Programming)

1. Định nghĩa
   1. Quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau và cấu trúc con tối ưu
   2. Nếu như bạn đã từng tham gia các cuộc thi code thuật toán hay các cuộc thi lập trình thì khoảng nửa đề thi bạn sẽ cần sử dụng tới Quy hoạch động, bởi khả năng giảm thời gian chạy của thuật toán đi đáng kể
   3. Nhìn vào định nghĩa Quy hoạch động, ta thấy ngay tính chất của quy hoạch động đó là Bài toán có các bài toán con gối nhau và cấu trúc con tối ưu. Nói là như vậy nhưng để nhận ra nó là điểu không dễ
2. Yêu cầu bài toán
   1. Bài toán lớn cần giải có thể phân rã được thành nhiều bài toán con. Trong đó, sự phối hợp lời giải của các bài toán con cho ta lời giải của bài toán lớn. Bài toán con có lời giải đơn giản được gọi là cơ sở của qui hoạch động. Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn được gọi là công thức truy hồi của qui hoạch động.
   2. Phải có đủ không gian vật lý lưu trữ lời giải các bài toán con (Bảng phương án của qui hoạch động). Vì qui hoạch động đi giải quyết tất cả các bài toán con, do vậy nếu ta không lưu trữ được lời giải các bài toán con thì không thể phối hợp được lời giải giữa các bài toán con.
   3. Quá trình giải quyết từ bài toán cơ sở (bài toán con) để tìm ra lời giải bài toán lớn phải được thực hiện sau hữu hạn bước dựa trên bảng phương án của qui hoạch động
   
   => Tóm lại để xây dựng được ta cần:
   
   1. Phân tách bài toán thành bài toán con: Công thức truy hồi
   2. Bảng phương án lưu kết quả của bài toán con
3. Phân tích
   Để hiểu hơn ta cùng phân tích một ví dụ cực kì đơn giản của quy hoạch động
   Tính số Fibonacy
   Ta có thể code đệ quy như thế này:

       int Fibonacy(int n){
           if(n==1||n==0) return 1;
           else return Fibonacy(n-1) + Fibonacy(n-2);
       }
               

   Hoặc sử dụng mảng như thế này:

       int n;cin>>n;
       int F[100]; F[1]=1; F[2] =1;
       for (int i=3; i<=n; i++)
       F[i] = F[i-1] + F[i-2];
       cout << F[n]
               

   Có thể bạn không tin nhưng cách code thứ 2 sử dụng mảng chính là sử dụng thuật toán Quy hoạch động đó
   2 thứ quan trọng của quy hoạch động là:
   
   1. Công thức truy hồi: F[n] = F[n-1] + F[n-2] với bài toán con ban đầu F[1]=1, F[2]=1
   2. Bảng phương án: F[] chứa các số Fibonacy theo thứ tự
4. Ví dụ
   1. Chuỗi con chung dài nhất
      
      1. Input:2 chuỗi kí tự s1,s2
      2. Output:Độ dài chuỗi kí tự con chung
      3. Nguyên tắc:
         
         1. bảng phương án: Mảng F[][]
         2. Công thức truy hồi: F[i][j]=F[i-1][j-1]+1 nếu s1[i]=s2[j]
                       =max(F[i-1][j],F[i][j-1]) trong các TH còn lại

      void QHD(string s1,string s2){
          int l1=s1.size(),l2=s2.size();
          int i,j;
          //khoi tao
          for(i=0;i < l1;i++)
              F[i][0]=0;
          for(i=0;i < l2;i++)
              F[0][i]=0;
          //tinh bang phuong an
              for(i=0;i < l1;i++)
                  for(j=0;j < l2;j++)
                      if(s1[i]==s2[j]){
                          F[i+1][j+1]=F[i][j]+1;
                      }
                      else {
                          F[i+1][j+1]=max(F[i+1][j],F[i][j+1]);
                      }
          //kq
              cout << F[l1][l2] << endl;
      }
                          

   2. Đổi tiền ATM
      
      1. Input:
         1. M: giá trị cần đổi tiền
         2. a[]: mảng các giá trị tiền nhỏ trong ATM, có thể cho trước hoặc nhập
      2. Output:Số đồng tiền nhỏ nhất cần để đổi giá trị tiền M
      3. Nguyên tắc:
         
         1. bảng phương án: Mảng F[][]
         2. Công thức truy hồi: F[i][j]=F[i-1][j-a[i]]+1 nếu j>a[i]
                       =F[i-1][j] trong các TH còn lại

      int a[100]={0,1,2,5,10,20,50,100,200,500,1000};
      int qhd(){  
          // khoi tao
          f[0][0]=0;
      	for(int i=1;i<=M;i++) f[0][i]=M+1;
      	for(int i=1;i<=10;i++) f[i][0]=0;
      	//bang phuong an
      	for(int i=1;i<=10;i++)
      	   for(int j=1;j<=M;j++)
      	   {
      	   	  f[i][j]=f[i-1][j];
      	   	  if(j>=a[i])
      	   	  f[i][j]=f[i][j-a[i]]+1;
             }
          //ket qua
      	cout << f[10][M] << endl; //n=10: Sl đồng tiền nhỏ trong ATM hay a.size()=10;
      }
                              

   3. Ngoài ra các bạn có thể tham khảo các dạng bài QHD phổ biến khác tại: liên kết