Mở đầu

Chỉ là một kĩ thuật Quy hoạch động thôi nhưng có rất nhiều bài toán sử dụng, tuy cùng bản chất nhưng cách áp dụng quy hoạch động cho mỗi bài toán lại rất khác nhau. Để hiểu rõ hơn cách tiếp cận một bài toán sử dụng quy hoạch động, mình sẽ trình bày qua các ví dụ được minh họa chi tiết nhất có thể. Cách tiếp cận sẽ từ “ngây thơ” nhất đến “chuẩn chỉnh”. Nếu bạn mới bắt đầu tìm hiểu về quy hoạch động thì có thể tham khảo bài viết trước.

Bài toán đồng xu

Đề bài của bài toán được phát biểu như sau:

Cho bạn các đồng xu có giá trị c1,c2,…,ckc_1, c_2,…, c_kc1​,c2​,...,ck​. Nhiệm vụ của bạn là lấy ít xu nhất có thể sao cho tổng giá trị của chúng bằng $T$ cho trước. Lưu ý rằng, không giới hạn số lần sử dụng một loại đồng xu.

Phân tích bài toán

Dạo khắp các bài hướng dẫn về quy hoạch động ta đều thấy tác giả dùng bài này làm ví dụ, giông như “Hello world” của quy hoạch động vậy . Cũng không ngoại lệ, nhưng mình sẽ cố gắng diễn giải cách tiếp cận bài toán này từ A tới Z, dễ hiểu và chi tiết nhất.

Dấu hiệu phổ biến để nhận diện các bài toán “có thể” sử dụng quy hoạch động là đề bài thường có các từ như “tối thiểu” cái này, “tối đa” cái kia, hoăc là “đếm số cách” để thỏa mãn điều kiện cho trước. Như trong bài toán đồng xu, ta đã thấy dấu hiệu ngay từ đề bài đó là “ít xu nhất”, cụ thể là “lấy ít xu nhất để cho tổng giá trị các đồng xu bằng $T$“. Nhưng đó là cảm quan ban đầu, hãy phân tích một cách logic hơn bài toán này.

Vấn đề khi sử dụng chiến thuật “tham lam”

Hãy xét một ví dụ cụ thể sau: Cho $3$ loại động xu có giá trị lần lượt là $1,2,5$. Nhiệm vụ của bạn là lấy ít xu nhất có thể sao cho tổng giá trị của chúng bằng tổng $12$.

Dễ thấy phương án tối ưu cho ví dụ này là lấy $1$ đồng xu giá trị $2$ và $2$ đồng xu giá trị $5$. Tổng giá trị là $5+5+2=12$. Cách tiếp cận một cách rất tự nhiên là ta sẽ sử dụng chiến thuật “tham lam”. Cụ thể là luôn luôn chọn đồng xu có giá trị lớn nhất có thể miễn là tổng giá trị của chúng không vượt quá giới hạn tổng giá trị của đề bài. Ví dụ, với bài toán trên ta sử dụng chiến thuật “tham lam” như sau:

• Lần chọn đầu, lấy $1$ đồng xu có giá trị lớn nhất là $5$.
• Tổng giá trị hiện tại là $5<T(T=12)$, do đó ta tiếp tục “tham lam” chọn đồng xu có giá trị lớn nhất là $5$.
• Tổng giá trị bây giờ là $10<T(T=12)$, vẫn nhỏ hơn tổng mục tiêu. Nếu bây giờ ta chọn đồng xu giá trị $5$ thì tổng sẽ thành $15>T$. Do đó, ở lần chọn này ta lấy đồng xu có giá trị 2.
• Quá vừa vặn, giờ đây tổng giá trị các đồng xu ta chọn bằng tổng mục tiêu trong đề bài và đó cũng là cách tối ưu nhất.

Hoàn hảo! Nhưng hãy nhớ tới bài viết trước, có một lưu ý là: Ta chỉ sử dụng “tham lam” nếu ta chứng minh được cách làm này là đúng đắn. Vậy ta phải xem xét kĩ một chút bài toán này trong một trường hợp khác.

Ví dụ tiếp theo: Cho $3$ loại động xu có giá trị lần lượt là $1,3,4$. Nhiệm vụ của bạn là lấy ít xu nhất có thể sao cho tổng giá trị của chúng bằng tổng $6$.

Giờ hãy thử sử dụng chiến thuật “tham lam” cho ví dụ này:

• Lần chọn đầu, với ý tưởng trên, ta chọn đồng xu có giá trị lớn nhất miễn sao tổng giá trị hiện tại không vượt quá tổng mục tiêu của đề bài. Do đó, ta chọn đồng xu có giá trị $4$.
• Tổng hiện tại là $4<T(T=6)$. Lần này ta không thể chọn đồng xu giá trị $4$ hoặc $3$ vì nó sẽ vượt quá tổng mục tiêu. Lần này ta chọn đồng xu giá trị $1$.
• Tương tự, ở lần chọn thứ $3$ ta tiếp tục chọn đồng xu giá trị $1$. Tổng hiện tại là $6$ thỏa mãn bài toán.

Bạn phát hiện rồi đó! Cách làm này chưa phải là tối ưu nhất. Cách làm tối ưu nhất là chọn $2$ đồng xu giá trị $3(3+3=6)$. Trong khi ở cách làm trên, ta phải sử dụng $3$ đồng xu $(4+1+1=6)$. Đây là ví dụ cho thấy việc sử dụng “tham lam” ở đây là hoàn toàn thất bại.

Tìm một cách giải chính xác

Để cẩn thận không bỏ xót các trường hợp, ta có thể sử dụng brute force duyệt qua tất cả các cách chọn xu. Tuy nhiên, với input lớn thì cách làm này thực thi cực kì chậm.

Do đó, ta có thể nghĩ cách sử dụng đệ quy ở đây. Bản chất của đệ quy là từ bài toán con được giải, ta kết hợp để giải bài toán cuối cùng. Quay trở lại bài toán đồng xu, “bài toán con” ở đây là gì?

Gọi $solve(x)$ là số lượng xu ít nhất có tổng giá trị là $x$. Ví dụ, cho $3$ đồng xu giá trị là $1,3,4$. Ta có các giá trị như sau:

$solve(0)=0$ -> $solve(1)=1$ -> $solve(2)=2$ -> $solve(3)=1$ -> $solve(4)=1$ -> $solve(5)=2$ -> $solve(6)=2$ -> $solve(7)$ = 2 -> $solve(8)=2$ -> $solve(9)=3$ -> $solve(10)=3$

Ví dụ, $solve(10)=3$ vì ta sẽ lấy 3 xu có giá trị lần lượt là $3,3,4$ có $3+3+4=10$.

Nhìn các giá trị trên dễ thấy rằng ta cần biết giá trị trước đó để tính toán cho các giá trị sau, dễ thấy một quy luật rằng: Số xu ít nhất cho tổng $T$ = số xu ít nhất cho tổng (T−ck)+1(T – c_k) + 1(T−ck​)+1 với ckc_kck​ là một giá trị của một đồng xu nào đó trong tập đồng xu đã cho. Và “+1” trong công thức chính là số lượng xu thêm.

Cụ thể, ta chuẩn hóa về dạng công thức truy hồi như sau

solve(x)=min(solve(x-1)+1,solve(x-3)+1,solve(x-4)+1)

Do đó các bài toán con của $solve(10)$ là $solve(9),solve(8)$,… Bài toán cơ sở là $solve(0)=0$.

Ngon roài! Đã có công thức truy hồi, giờ triển code thoai

intsolve(int x){if(x <0)return INF;// không có trường hợp tổng giá trị nhỏ hơn 0 nên gán bằng một số rất lớn nào đóif(x ==0)return0;int best = INF;for(auto c : coins){// Duyệt qua các giá trị của đồng xu
   best =min(best,solve(x-c)+1);}return best;}

Nhưng mà chờ đã, đoạn code trên là đệ quy mà, vậy thì ta sẽ phải lưu giá trị của các bài toán con như nào? Đoạn code dưới sẽ giúp các bạn:

int value[T+1]//T là tổng giá trị các đồng xu mà đề bài cho trước, value là số xu ít nhất để đạt tổng giá trị Tintsolve(int x){
  value[0]=0;for(int x =1; x <= n; x++){
    value[x]= INF;for(auto c : coins){//Với các giá trị c của đồng xuif(x-c >=0){
        value[x]=min(value[x], value[x-c]+1);}}}}

Vậy là ở đây, ta đã sử dụng mảng $value[T+1]$ để lưu giá trị và dùng tiếp cho lần tính toán sau. Việc này giúp ta tiết kiệm thời gian hơn là cách dùng Quy hoạch động.

Đôi khi không phải tìm ra giá trị tối ưu là xong, bài toán có thể yêu cầu ta tìm phương án tối ưu. Ví dụ cụ thể trong bài trên đó là, cần chọn những đông xu nào để đạt được tổng $T$ mà cần ít xu nhất. Với bài toán này, ta cần sửa một chút code ở trên. Ý tưởng là khai báo một mảng để lưu giá trị xu đầu tiên sẽ lấy ở mỗi tổng $T$ đảm bảo rằng cách chọn xu vẫn tối ưu. Đoạn code dưới giúp thực hiện ý tưởng đó (dưới đây là đoạn code thực hiện ý tưởng chính, để chạy được các bạn thêm các yếu tố khác cần thiết vào nhé!).

int first[N];

value[0]=0;for(int x =1; x <= n; x++){
  value[x]= INF;for(auto c : coins){if(x-c >=0&& value[x-c]+1< value[x]){
      value[x]= value[x-c]+1;
      first[x]= c;}}}while(n >0){
  cout << first[n]<<"n";
  n -= first[n];}

Vậy là mình đẫ trình bày toàn bộ hướng tư duy để giải một bài toán “Hello world” của quy hoạch động. Tất nhiên các bài toán quy hoạch động rất đa dạng và đòi hỏi cần luyện tập thường xuyên.

Dãy con tăng dài nhất

Ta sẽ xét tiếp tục với một ví dụ kinh điển khác. Nội dung bài toán là: Cho một mảng $A$ gồm các số nguyên $A[0],A[1],...,A[n-1]$. Nhiệm vụ của bạn là tìm một dãy con tăng dài nhất. Lưu ý rằng, dãy con này không cần thiết phải liên tục. Ví dụ: $n=8,A=\{-7,10,9,2,3,8,8,1\}$, kết qủa: Độ dài của dãy cần tìm là 4, dãy đó là $\{-7,2,3,8\}$.

Phân tích bài toán

Lời giải ngây thơ và cơ bản nhất cho bài toán này là ta sẽ duyệt qua toàn bộ dãy con có thể có trong mảng và chọn ra dãy con thỏa mãn. Tuy nhiên, tốc độ thực thi của cách làm này rất chậm, có độ phức tạp thời gian là O(2n)O(2^n)O(2n). Thay vì phải thử tất cả các trường hợp có thể, ta sẽ sử dụng một cách tiếp cận khác thông minh hơn đó là quy hoạch động.

Để sử dụng quy hoạch động bạn cần xác định được bài toán con và công thức truy hồi. Gọi hàm $solve(i)$ là hàm trả về giá trị độ dài dãy con lớn nhất tính từ phần tử đầu tiên (chỉ số là 0) đến phần tử thứ $i$. Dễ thấy rằng $solve(0)=1$, một phần tử cũng là một dãy con. Với $i\ge 1$, bài toán trở nên phức tạp hơn. Ta cần chỉ số $j$ sao cho $j<i$, $A[i]>A[j]$ và $solve(i)$ là lớn nhất. Khi tìm được chỉ số $j$, ta có $solve(i)=solve(j)+1$. Vậy ta đã có đủ nguyên liệu cho cách tiếp cận quy hoạch động. Thuật toán được mô tả như sau:

• $solve(0)=1$ đây là bài toán cơ sở.
• $solve(i)=solve(j)+1$, $\forall j\in [0,...,i-1]$ và $A[i]>A[j]$
• Đáp án lớn nhất của bài toán là giá trị lớn nhất của $solve(k)$ với $\forall k\in [0,...,n-1]$

Độ phức tạp của thuật toán này là O(n2)O(n^2)O(n2).

Với ý tưởng đầu tiên ta dễ dàng triển khai code như sau:

for(int i =0; i < n; i++){
  solve[i]=1;for(int j =0; j < i; j++){if(array[j]< array[i]){
      solve[i]=max(solve[i],solve[j]+1);}}}

Tuy nhiên, ta có thể cải tiến thuật toán này về độ phức tạp $O(n\log k)$ (trong đó $k$ là độ dài của dãy con tăng dài nhất) sử dụng thuật toán tham làm và chia để trị. Cách giải này được đề cập trong sách Competitive programming 3 (đính kèm bên dưới). Ý tưởng là, duy trì một mảng luôn được sắp xếp và từ đó có thể áp dụng với tìm kiếm nhị phân. Gọi mảng $L$ là một mảng sao cho $L(i)$ đại diện cho giá trị kết thúc nhỏ nhất của tất cả các dãy con tăng dài nhất có độ dài $i$ được tìm từ trước đó. Như vậy, ta có thể tìm kiếm nhị phân mảng $L$ để xác định dãy con tăng dài nhất có thể mà ta có thể tạo bằng cách thêm phần tử hiện tại $A[i]$ — chỉ cần tìm chỉ số của phần tử cuối cùng trong $L$ nhỏ hơn $A[i]$. Thuật toán được thực thi như sau:

• Ban đầu, tại $A[0]=-7$, ta có $L=\{-7\}$.
• Ta có thể chèn $A[1]=10$ tại $L[1]$ để có dãy con tăng dài nhất có độ dài là 2, $L=\{-7,10\}$.
• Với $A[2]=9$, ta thay thế $L[1]$ để có phần tử cuối dãy con tăng dài nhất là 9: $L=\{-7,9\}$. Đây là một chiến lược tham lam. Bằng cách lưu trữ dãy con tăng dài nhất với giá trị cuối nhỏ hơn, ta tối đa hóa khả năng mở rộng dãy con tăng dài nhất hơn nữa với các giá trị trong tương lai.
• Đối với $A[3]=2$, ta thay thế $L[1]$ kết thúc dãy con tăng dài nhất: $L=\{-7,2\}$.
• Tiếp theo chèn $A[4]=3$ tại $L[2]$ để ta có dãy con tăng dài nhất dài hơn, $L=\{-7,2,3\}$.
• Chèn $A[5]$ = 8 tại $L[3]$ để ta có dãy con tăng dài nhất dài hơn, $L=\{-7,2,3,8\}$.
• Đối với $A[6]=8$, không có gì thay đổi vì $L[3]=8$. $L=\{-7,2,3,8\}$ không đổi.
• Với $A[7]=1$, ta cải tiến $L[1]$ sao cho $L=\{-7,1,3,8\}$. Khi thay $L[1]=1$ ta có mảng $L$ không phải dãy con tăng dài nhất. Bước này rất quan trọng vì trong một số trường hợp có thể có các dãy con dài hơn trong tương lai có thể kéo dài dãy con độ dài 2 tại $L[1]=1$. Ví dụ, hãy thử với mảng sau: $A=\{-7,10,9,2,3,8,8,1,2,3,4\}$. Độ dài của dãy con tăng dài nhất cho mảng này là 5.
• Câu trả lời là độ dài lớn nhất của mảng $L$ được sắp xếp ở cuối quá trình.

Với ý tưởng cải tiến thuật toán quy hoạch động, ta có code hoàn chỉnh sau đây:

#include<bits/stdc++.h>usingnamespace std;#defineMAX_N100000voidprint_array(constchar*s,int a[],int n){for(int i =0; i < n;++i){if(i)printf(", ");elseprintf("%s: [", s);printf("%d", a[i]);}printf("]n");}voidreconstruct_print(int end,int a[],int p[]){int x = end;
  stack<int> s;for(; p[x]>=0; x = p[x]) s.push(a[x]);printf("[%d", a[x]);for(;!s.empty(); s.pop())printf(", %d", s.top());printf("]n");}intmain(){int n =11, A[]={-7,10,9,2,3,8,8,1,2,3,4};int L[MAX_N], L_id[MAX_N], P[MAX_N];int LIS =0, lis_end =0;for(int i =0; i < n;++i){int pos =lower_bound(L, L + LIS, A[i])- L;//binary search
    L[pos]= A[i];
    L_id[pos]= i;
    P[i]= pos ? L_id[pos -1]:-1;if(pos +1> LIS){
      LIS = pos +1;
      lis_end = i;}printf("Considering element A[%d] = %dn", i, A[i]);printf("LIS ending at A[%d] is of length %d: ", i, pos +1);reconstruct_print(i, A, P);print_array("L is now", L, LIS);printf("n");}printf("Final LIS is of length %d: ", LIS);reconstruct_print(lis_end, A, P);return0;}

Tổng kết

Vậy ta đã tìm hiểu cách tiếp cận $2$ bài toán sử dụng quy hoạch động kinh điển. Các phần sau, ta sẽ tiếp tục tìm hiểu những bài toán có cách xử lý phức tạp hơn.

Tài liệu tham khảo

1. Giải thuật và lập trình – Thầy Lê Minh Hoàng
2. cp-algorithms.com
3. Handbook Competitive Programming – Antti Laaksonen
4. Competitve programming 3 – Steven Halim, Felix Halim