Nguồn: Topcoder, VNOI Wiki

(Intermediate & Upper Intermediate & Advanced coming soon.)

Có rất nhiều bài toán được áp dụng quy hoạch động (QHĐ) (Dynamic Programming). QHĐ là một trong những kĩ thuật quan trọng. Bài viết này sẽ giúp bạn hiểu được QHĐ thông qua các ví dụ cụ thể.

Note: Trong bài này có thể có nhiều phần bạn đã biết, bạn hoàn toàn có thể chuyển qua đọc phần khác.

---

Beginner

Quy hoạch động là gì ?

QHĐ là kĩ thuật được được dùng khi có một công thức và một (hoặc một vài) trạng thái bắt đầu. Một bài toán được tính bởi các bài toán nhỏ hơn đã tìm ra trước đó. QHĐ có độ phức tạp đa thức nên sẽ chạy nhanh hơn quay lui và duyệt trâu.

Để hiểu rõ hơn hãy xem ví dụ sau:

Cho $N$ đồng xu và giá tiền của mỗi đồng $(V_0,V_1,\dots ,V_{N-1})$, và số $S$. Tìm số đồng xu nhỏ nhất để tổng giá trị của chúng bằng $S$ (số lượng đồng xu không giới hạn).

Bây giờ chúng ta sẽ xây dựng thuật giải:

Đầu tiên, cần tìm một trạng thái của bài toán.

Trạng thái là gì ?

Trạng thái là một trường hợp, một bài toán con của bài toán lớn. Ví dụ, trạng thái trong bài này là số lượng xu nhỏ nhất để tổng bằng $i$, với $i\le S$. Để tìm ra trạng thái $i$, cần phải tìm tất cả các trạng thái $j$ mà $(j<i)$. Một khi đã tìm ra trạng thái $i$, ta có thể dễ dàng tìm ra trạng thái của $i+1$.</p>

Làm thế nào để tìm được ?

Với mỗi $j$, $V_j\le i$, tìm số đồng xu nhỏ nhất để tổng bằng $i-V_j$. Giả sử nó bằng $m$. Nếu $m+1$ nhỏ hơn số lượng đồng xu hiện tại cho tổng $i$ thì ta cập nhập nó bằng $m+1$.

Sau đây là ví dụ: Cho các đồng xu với giá tiền $1,3,5$. Và $S=11$. Đầu tiên, ta bắt đầu từ trạng thái $0$, chúng ta có $f[0]=0$. Xét đến tổng $1$. Có duy nhất đồng xu $1$ nhỏ hơn hoặc bằng tổng $1$, nên ta có

$f[1]=f[1-V0]+1=f[0]+1=1$. Xét đến tổng $2$. Cũng giống như tổng trước, chỉ có $1$ đổng xu $\le 2$, có

$f[2]=f[2-V_0]+1=f[1]+1=2$ Đến tổng $3$. Lần này có $2$ đồng xu $\le 3$ là $1$ và $3$. - Nếu ta chọn đồng $1$, ta có

$f[3]=f[3-V_0]+1=f[2]+1=3$ - Nếu ta chọn đồng 3, ta có

$f[3]=f[3-V_1]+1=f[0]+1=1$ Rõ ràng là $1\le 3$ nên ta chọn đồng $3$ và $f[3]=1$ Xét tiếp đến tổng $4$, rồi đến $11$ bằng cách như trên.

Mã giả:

Gán Min[i] bằng dương vô cùng với mọi i
Min[0]=0

For i = 1 to S
For j = 0 to N - 1
   If (Vj<=i AND Min[i-Vj]+1<Min[i])
Then Min[i]=Min[i-Vj]+1
Output Min[S]

Đây là lời giải cho tất cả các tổng:

Vậy là chúng ta đã tìm được lời giải cho $3$ đồng xu tổng bằng $11$. Dựa vào bảng trên, ta có thể truy vết lại được những đồng xu nào được chọn để tối ưu bài toán. Bài QHĐ trên còn có một cách tiếp cận khác nữa. Lần này, ta sẽ không tính liên tiếp các tổng. Bắt đầu từ trạng thái $0$. Thử nhét đồng xu thứ $1$ vào các tổng đã tính. Nếu như tổng $t$ có số đồng xu ít hơn số đồng xu hiện tại thì tiến hành cập nhật. Rồi tiếp tục thử với đồng thứ $2,3$ cho đến khi thử hết các đồng. Ví dụ, nhét đồng $1$ (giá trị $1$) vào tổng $0$ ta có tổng $1$. Vì ta chưa tính tổng $1$ nên $S[1]=1$. Nhét đồng $1$ vào tổng $1$ ta có $S[2]=2$. Tiếp tục làm như vậy với các tổng còn lại. Sau đồng $1$, ta nhét đồng $2$(giá trị $3$) vào tổng $0$ ta được $1$, mà $S[3]=3>1$, ta cập nhật $S[3]=1$. Tiếp tục nhét đồng $2$ vào các tổng còn lại, cũng như thử nhét các đồng xu khác.

---

Elementary

Bây giờ, chúng ta cùng đến một khái niệm mới, công thức truy hồi (recurrent relation), mối liên hệ giữa những trạng thái.

Ví dụ: Cho một dãy $N$ số - $A[1],A[2],\dots ,A[N]$. Tìm dãy con không giảm dài nhất.

Ta quy định trạng thái $S[i]$ là dãy con không giảm dài nhất kết thúc tại $A[i]$. Với $i>1$ và $j<i$, tính được $i$ khi tồn tại $A[j]\le A[i]$ (vì đây là dãy không giảm). Khi đó $S[i]=Max(S[i],S[j]+1)$. Tiếp tục tính như vậy cho đến khi đến được trạng thái $S[N]$.</p>

Hãy xem bảng sau với dãy: $5,3,4,8,6,7$:

Bài luyện tập: Cho đồ thị vô hướng $G$ có $N$ đỉnh $(N\le 1000)$ và các cạnh có trọng số dương. Tìm đường đi ngắn nhất từ đỉnh $1$ đến đỉnh $N$ hoặc thông báo không tồn tại đường đi. Gợi ý: Tại mỗi bước, chọn ra trong số các đỉnh chưa thăm mà có đường đi từ $1$, chọn ra đỉnh có đường đi ngắn nhất.

Các bài ví dụ khác:

• ZigZag - 2003 TCCC Semifinals 3.
• BadNeighbors - 2004 TCCC Round 4.
• FlowerGarden - 2004 TCCC Round 1.