Embedded Files
Nguồn tài liệu:
Competitive Programming 4, Steven Halim
Tài liệu chuyên Tin quyển 1, Hồ Sỹ Đàm
GeeksforGeeks - Dynamic Programming
Giới thiệu
Giới thiệu
Qua các tư tưởng bàn ở trên, chúng ta thấy rằng giải thuật chia để trị dùng đệ quy có thể đưa ra được đáp án chính xác cho bài toán, quay lui vét cạn kết hợp với nhánh cận cũng có thể đưa ra được kết quả tối ưu cho một số bài toán trong thời gian cho phép. Tuy nhiên các giải thuật dựa trên các tư tưởng này vẫn phụ thuộc vào tập dữ liệu đầu vào và có khả năng không thể giải quyết được với những bài toán có input quá lớn. Giải thuật tham làm khắc phục được về mặt thời gian cho các bài toán tối ưu do dựa trên chiến lược lựa chọn phương án tối ưu cục bộ nhưng lại cũng phụ thuộc vào tập dữ liệu vào. Rất nhiều trường hợp giải thuật tham cho ra kết quả sai.
Cho đến thời điểm hiện tại, quy hoạch động có lẻ là giải pháp tối ưu phổ biến nhất cho các bài toán dựa trên đệ quy và có khả năng khắc phục được hạn chế của các giải thuật nêu trên. Chủ đề này thảo luận qua về tư tưởng chính của quy hoạch động, các bước tiến hành giải bài toán bằng quy hoạch động, phân biệt các phương án triển khai quy hoạch động thông qua một số bài toán điển hình.
Bài toán mở đầu
Bài toán mở đầu
Tư tưởng chính của quy hoạch động là dựa vào sự lưu trữ kết quả. Nếu trong phương pháp chia để trị, chúng ta phân rã bài toán thành các bài toán con, thực hiện giải các bài toán con rồi dùng công thức hồi quy để kết hợp chúng trở lại cho ra kết quả bài toán lớn. Trong quá trình đó, các bài toán con trùng lặp lại rất nhiều lần và đó cùng chính là lý do làm cho giải thuật này trở nên chậm. Vậy thì trong quy hoạch động, chúng ta tìm cách lưu trữ lại kết quả các bài toán con để khi cần đến chúng ta chỉ việc lấy ra tính toán, thì hiệu quả về mặt thời gian sẻ nhanh hơn rất nhiều.
Để thấy rõ vấn đề trên, chúng ta cùng nhìn lại một bài toán kinh điển: Dãy Fibonaci
Nguồn ảnh: SGK chuyên tin 1, Hồ Sỹ Đàm
Từ định nghĩa dãy số Fibonaci như trên ta dễ dàng cài đặt một giải thuật đệ quy một cách tự nhiên như sau:
#include <iostream>
using namespace std;
int F(int n){
if(n <=1) return n;
else return F(n-1) + F(n-2);
}
int main(){
int n;
cin>>n;
cout<<F(n);
return 0;
}
Cách cài đặt trên nhìn vào rất dễ hiểu, nhưng khi thực hiện với số lớn sẽ gặp vấn đề vì số bài toán con cần giải lại trùng lặp rất nhiều lần. Ví dụ với n =5, quá trình tính toán thực hiện như sau:
Nguồn ảnh: https://www.baeldung.com/
Chúng ta sẽ thấy F(0), F(1), F(2) được tính toán lại nhiều lần, nếu với n = 100, số lượng này tằng lên đáng kể. Để khắc phục tình trạng trên, tư tưởng quy hoạch động là tìm cách lưu lại kết quả các bài toán con, để khi gọi đến sẽ trả ra kết quả trực tiếp mà không cần tính nữa.
Chúng ta quan sát cách lưu thứ nhất như sau:
#include <iostream>
#include <cstring>
using namespace std;
int S[50];
int F(int n){
if (S[n] != -1) return S[n];
else{
if(n <=1) return n;
else S[n] = F(n-1) + F(n-2);
}
return S[n];
}
int main(){
int n;
cin>>n;
memset(S, -1, sizeof(S));
cout<<F(n);
return 0;
}
Với cách này, chúng ta dùng mảng S[] lưu lại kết quả các bài toán con, khi được gọi đến, nó sẽ không phải tính nữa mà đơn giản là trả về kết quả của bài toán đó vì đã được lưu trong S. Vẫn với n = 5, lúc này quá trình thực thi sẽ thể hiện như sau:
Nguồn ảnh: https://www.baeldung.com/
Chúng ta thấy rằng số lần tính toán chỉ còn đúng N lần. Cách lưu giá trị như trên được gọi là nhớ trạng trái (Memozation) và cách cài đặt như vậy chúng ta gọi là quy hoạch hoạch động kiểu Top-Down.
Chúng ta cũng có thể dùng cách thứ 2 để lưu kết quả bài toán con như sau:
#include <iostream>
using namespace std;
int S[50];
int F(int n){
S[0] = 0;
S[1] = 1;
for (int i = 2; i<=n; i++){
S[i] = S[i-1] + S[i-2];
}
return S[n];
}
int main(){
int n;
cin>>n;
cout<<F(n);
return 0;
}
Mảng S[] vẫn được dùng để lưu kết quả các bài toán con. Tuy nhiên, khác với cách lưu ở trên, ở cách này chúng ta tính giá trị các bài toán con bắt đầu từ bài toán nhỏ nhất rồi tiền dần lên đến khi đạt được giá trị bài toán cuối cùng. Quá trình thực thi diễn ra như sau:
Cách lưu này được gọi là dùng bảng (Tabulation), cách cài đặt này gọi là quy hoạch động kiểu Bottom-up
Nguồn ảnh: https://www.baeldung.com/
Ví dụ trên phần nào đã giúp chúng ta có cái nhìn ban đầu về quy hoạch động. Tuy nhiên, bài toán tìm số Fibonaci thứ n là bài toán kinh điển và rất dễ nhận ra cách cài đặt đệ quy truyền thống hay cải tiến bằng quy cách lưu giá trị của quy hoạch động. Nếu gặp một bài toán phức tạp hơn, làm sao chúng ta có thể giải được với phương pháp này? Một số bước gợi ý giúp chúng ta tiếp cận như sau:
Các bước giải bài toán quy hoạch động
Các bước giải bài toán quy hoạch động
Bước 1. Xác định đây có phải là bài toán quy hoạch động hay không?
Bước 2. Xác định cách biểu diễn trạng thái với ít tham số nhất
Bước 3. Tìm công thức hồi quy để chuyển từ trạng thái bài toán con về trạng thái của bài toán lớn
Bước 4. Tìm cách lưu kết quả các bài toán con (Memozation hoặc Tabulation)
Chúng ta dành chút thời gian để thảo luận về bốn bước trên.
Bước 1 - Xác định đây có phải là bài toán quy hoạch động hay không
Bước này khá quan trọng, nếu chúng ta đánh giá sai, có thể sẽ đi tìm cách giải một bài toán bằng phương pháp quy hoạch động trong khi nó không thể. Các bài toán yêu cầu chúng ta tìm phương án tối ưu như tối đa hay tối thiếu, hay đếm số lượng phương án gì đó thường là những bài toán quy hoạch động.
Các bài toán quy hoạch động cũng phải đảm bảo tính chất bài toán con trùng lặp và cấu trúc con tối ưu (như đã bàn ở giải thuật tham lam.
Bước 2 - Xác định cách biểu diễn trạng thái với số lượng tham số tối thiểu.
Hầu hết các bài toán giải bằng quy hoạch động đều liên quan đến các trạng thái và việc chuyển trạng thái. Nên chúng ta phải mô tả được trạng thái bài toán thì mới có thể quyết định cách thức chúng ta đưa bài toán từ lớn xuống nhỏ rồi hồi quy ngược trở lên. Nói một cách nôm na là chúng ta xác định tên trạng thái và các giá trị đại diện cho trạng thái vào thời điểm đó. Nó gần như phát biểu gọi F[i][j] là giá trị tối đa của F tại thời điểm i với j vật thể bay vào.
Bước 3 - Tìm công thức hồi quy
Đây là bước khó nhất và đòi hỏi nhiều kinh nghiệm, trực giác và quá trình luyện tập. Đa phần các bài toán quy hoạch động thì các trạng thái sau được tính dựa vào giá trị trạng thái trước đó. Nên mấu chốt vấn đề nằm ở chỗ chúng ta tìm ra được mối tương quan, hay một công thức dùng để kết hợp giá trị các bài toán con trước đó thành giá trị bài toán lớn. Công thức đó có thể là lựa chọn giá trị lớn nhất, nhỏ nhất trong các bài toán trước, hay số lượng tại trạng thái trước đó cộng, trừ, nhân, chia cho giá trị nào đó, ...
Bước 4 - Xác định cách lưu
Tùy theo thói quen, kinh nghiệm hay lựa chọn triển khai theo kiểu Top-Down hay Bottom-Up mà chúng ta lưu theo dạng Memozation hay Tabulation. Tuy nhiên, số chiều của thùng chứa mà chúng ta dùng làm bảng lưu đó thường phụ thuộc vào số chiều chúng ta chặt nhỏ bài toán. Ví dụ như với bài toán tính giai thừa một số nguyên, chúng ta chặt bài toàn nhỏ dần trên chính số đó, chỉ một mình số đó và được giảm dần đến khi gặp neo. Nhưng với bài toán tìm xâu con chung dài nhất của hai xâu A, B, ta phải chặt nhỏ dần cả hai xâu để so với xâu còn lại, nên bảng lưu sẽ là bảng hai chiều.
Chúng ta cùng xét qua một số ví dụ sau đây để dần tiếp cận vấn đề.
Một số ví dụ
Một số ví dụ
Tóm tắt: Cho trước những lựa chọn khác nhau của các set đồ ( ví dụ: 3 áo sơ mi, 2 cà vạt, 4 giầy, ...) và một ngân quỹ giới hạn. Nhiệm vụ của chúng ta là mua một bộ gồm đủ các thành phần của bộ đồ trên, mỗi thứ một cái. Chúng ta không được xài quá ngân quỹ nhưng lại muốn xài sao cho số tiền lớn nhất có thể.
Dữ liệu vào:
Dòng đầu gồm 2 số nguyên 1<=M <=200, 1<=C<=20, trong đó M là ngân quỹ còn C là số lượng set đồ.
C dòng tiếp theo, mỗi dòng chứa các số nguyên cách nhau bằng khoảng trắng:
-Số đầu tiên là 1<=K<=20 là số lượng models trong set đó,
-Theo sau là K số nguyên, là giá tiền của từng model
Output:
Một số nguyên duy nhất là số tiền tối đa có thể tiêu mà mua đủ mỗi set một món. Nếu không thể mua được thì xuất ra "No solution"
Chẳng hạn với testcase 1:
M = 20, C = 3, giá của các models trong 3 sets đồ được cho như sau:
g0: 6 4 8
g1: 5 10
g2: 1 5 3 5
Kết quả tối ưu cho testcase này là 19, gồm các cách chọn: 8+10+1, 6 + 10 + 3 hoặc 4 + 10 + 5.
Tuy nhiên testcase 2:
M = 9, C = 3
g0: 6 4 8
g1: 5 10
g2: 1 5 3 5
Kết quả sẻ là "no solution", vì dù ta có chọn hai model rẽ nhất ở g0, g1 là 4 + 5 thì cũng không còn tiền để mua model thứ 3. Chúng ta thử thảo luận qua một vài hướng tiếp cận cho bài toán này.
Hướng tiếp cận 1 - Tham lam (greedy)
Vì ta muốn sử dụng tối ta số tiền nên tại mỗi set đồ (gi) ta chọn món có giá cao nhất mà nhỏ hơn số tiền còn lại, cho đến khi đủ C models. Với testcase 1, đầu tiên chọn 8, số tiền còn lại 12, chọn tiếp 10, còn lại 2 và cuối cùng chọn 1. Kết quả là 19 đúng là kết quả tối ưu.
Với testcase 2, đầu tiên cũng chọn 8, còn lại 1, không thể chọn tiếp model nào ở set 2 nên ra kết quả "no solution". Giải thuật tham lam này chạy rất nhanh. Trong trường hợp xấu nhất ta cũng chỉ tốn 20 x 20 = 400 phép tìm max, trừ, cộng. Tuy nhiên không phải lúc nào giải thuật này cũng đúng, ví dụ với testcase 3:
M = 12, C = 3
g0: 6 4 8
g1: 5 10
g2: 1 5 3 5
Giải thuật trên cho ra kết quả "no solution", tuy nhiên, kết quả tối ưu của test này là đúng 12: 4 + 5 + 3
Hướng tiếp cận 2 - Chi để trị (Divide and Conquer)
Bài này không thể giải bằng chia để trị, do cấu trúc bài toán con không độc lập. Bước chọn sau bị phụ thuộc vào bước chọn trước đó, nên không thể chia nhỏ bài toán rồi giải từng phần và kết hợp lại được.
Hướng tiếp cận 3 - Quay lui (backtracking, complete search)
Để có thể backtrack cho bài toán này, trước tiên ta cần mô hình hóa nghiệm của nó: là một vector x với chiều dài C. mỗi ô x_i được điền giá trị trong set đồ g_i. Để có thể nhảy từ ổ $\x_i$ sang ô x_(i+1), ta cần mô hình hóa bài toán bằng một hàm dp(g, b) với ý nghĩa rằng ta cần chọn món đồ g với ngân quỹ còn lại là b.
Bắt đầu với g = 0 (set đồ đầu tiên), lúc này b = M (chưa xài tiền). Ta thử lần lược từng model trong g0 (20 model), nếu ta chọn model thứ i thì ngân quỹ b = M - g0[i] (giá của món thứ i). Chọn xong 1 món ở set g0 thì ta nhảy qua g1, lặp lại quá trình này cho đến khi thỏa điều kiện nghiệm (đủ C món) hoặc b = 0, đã xài hết tiền. Cứ mỗi lần chọn đủ một bộ C món, ta cập nhật lại ngân quỹ Max = M - b (số tiền thật sự đã xài).
Giải thuật có thể được tóm tắt lại như sau:
Bước 1. If b < 0, dp(g, b) = -∞ (trong khi code thực tế, ta gán giá trị này bằng - MAX_INT)
Bước 2. If món đồ cuối cùng được chọn, thỏa đk nghiệm, dp(g, p) = M-b (số tiền thực sự đã xài)
Bước 3. Tổng quát, với mọi món đồ của các set, dp(g, p) = max(dp(g+1, b - price[g][model]) --> chúng ta cần tìm max của giá trị này.
Giải thuật này tức nhiên luôn cho ra kết quả chính xác nhưng sẽ rất chậm. Chúng ta cần vét hết 20 món đồ trong mỗi set và phải điền vào 20 ô cho vector nghiệm --> 20^20 ⇔ 10^26, đây là con số rất lớn phép toán và chắc chắn không thể chạy trong thời gian cho phép.
Hướng tiếp cận 4 - Quy hoạch động Top-Down (Top-Down DP)
Quay lại với bốn bước tiến hành giải bài toán quy hoạch đồng ở phần giới thiệu, bước đầu tiên chúng ta cần đảm bảo bài toán này giải được bằng phương pháp quy hoạch động.
Bài toán này có cấu trúc con tối ưu:
Theo cách phân rã bài toán ở phương pháp backtracking trên, ta thấy rằng cấu trúc tối ưu của bài toán con nằm trong cấu trúc tối ưu của bài toán ban đầu. Ví dụ như ta chọn một món đồ ở set g0 thì bước tiếp theo phải chọn tiếp món đồ ở g1 với ngân quỹ M-price, price là giá món đồ đã chọn trước đó.
Bài toán này có các bài toán con trùng lắp:
Đây là tính chất quyết định của DP, rõ ràng trong quá trình phân rã bài toán ở trên, sẽ có rất nhiều bài toán con tối ưu trùng lại giá trị của bài toán con khác trước đó.
Chẳng hạn như trong một set gi có hai món đồ trùng giá p, vậy rõ ràng khi ta đưa về bài toán con dp(g+1, b-p) sẽ ra cùng một bài toán.
Như vậy có nghĩa trong 10^26 khả năng ta nói trong giải pháp backtracing, thực chất chỉ có 20 x 201 bài toàn con khác nhau đôi một. Trong đó g chạy từ 0 đến 19 còn b chạy từ 0 đến 200. Mỗi bài toán chỉ giải đúng một lần.
Giải thuật quy hoạch động cho bài toán này theo hướng Top-Down sẽ dựa trực tiếp vào ba bước của backtracking ở trên và thêm hai bước sau đây:
Bước 4. Chọn bảng lưu kết quả bài toán con (Memo Table)
Nhờ bảng lưu này, mỗi lần gặp lại bài toán con cùng trạng thái, nó sẽ trả ra kết quả bằng cách truy cập vào chỉ số mảng tại trạng thái đó trong O(1). Bảng lưu này phụ thuộc vào cách ta mô hình hóa bài toán. Ở trên ta mô hình trạng thái dạng dp(g, b), như vậy ta tạo một bảng hai chiều, ô [g][b] lưu giá trị tiền nếu chọn model g với ngân quỹ giới hạn b.
Trong cách giải quy hoạch động theo hướng Top-down, bảng nhớ (Memo Table) thường được khởi tạo trước giá trị cho tất các ô là 0 hoặc -1.
Bước 5. Tại thời điểm bắt đầu của hàm đệ quy, ta kiểm tra xem bài toán đã được tính toán chưa.
Nếu rồi thì trả ra giá trị tại ô tương ứng của bảng.
Nếu chưa thì tính giá trị cho ô đó (dử dụng công thức hồi quy đã phân tích ở giải pháp backtracking).
Hàm được viết như sau:
// UVa 11450 - Wedding Shopping - Top Down
// this code is similar to recursive backtracking code
// parts of the code specific to top-down DP are commented with: `TOP-DOWN'
// if these lines are commented, this top-down DP will become backtracking!
#include <bits/stdc++.h>
using namespace std;
const int MAX_gm = 30; // up to 20 garments at most and 20 models/garment
const int MAX_M = 210; // maximum budget is 200
int M, C, price[MAX_gm][MAX_gm]; // price[g (<= 20)][k (<= 20)]
int memo[MAX_gm][MAX_M]; // TOP-DOWN: dp table [g (< 20)][money (<= 200)]
int dp(int g, int money) {
if (money < 0) return -1e9; // fail, return -ve number
if (g == C) return M-money; // we are done
// if the line below is commented, top-down DP will become backtracking!!
if (memo[g][money] != -1) return memo[g][money]; // TOP-DOWN: memoization
int ans = -1; // start with a -ve number
for (int k = 1; k <= price[g][0]; ++k) // try each model k
ans = max(ans, dp(g+1, money-price[g][k]));
return memo[g][money] = ans; // TOP-DOWN: memoize ans
}
Nguồn: Steven Halim github - CPBook Code - Chapter 3
Độ phức tạp:
Như đã phân tích ở trên, chúng ta có 20 * 201 = 4020 bài toán con, mỗi bài toán con chọn trong 20 món đồ, vậy tổng cộng có 4020 * 20 = 80 400 phép toán cho mỗi testcase.
Hướng tiếp cận 5 - Quy hoạch động Bottom-Up (Bottom-Up DP)
Đúng như tên gọi, Bottom-Up DP cùng dùng bảng lưu giá trị bài toán con nhưng ngược với Top-Down, bảng giá trị này được tính từ bài toán cơ sở tính lên đến bài toán lớn.
Các bước tiến hành như sau:
Bước 1. Xác định số chiều của bảng lưu dựa vào số tham số cần quan tâm (tương tự như phân tích Backtracking)
Bước 2. Chuẩn bị sẵn mảng lưu (Tabular) theo số chiều đã phân tích ở trên, tính sẵn các giá trị cơ sở. Lưu ý chỗ này khác bảng Memo Table của Top-Down. Trong Top-Down, Memo Table được điền hết với giá trị -1, ngụ ý các bài toán này chưa được giải. Còn trong Bottom-Up, Tabular chỉ tính sẵn các ô chứa bài toán cơ sở.
Bước 3. Xác định những ô tiếp theo có thể điền dựa vào công thức hồi quy. Cứ điền dần cho đến hết bảng.
Với bài toán này, các bước Bottom-up được tiền hành như sau:
Chúng ta dùng lại testcase 2 như trên để minh họa:
M = 20, C = 3, giá của các models trong 3 sets đồ được cho như sau:
g0: 6 4 8
g1: 5 10
g2: 1 5 3 5
Kết quả tối ưu cho testcase này là 19
Chúng ta sẽ mô hình hóa bài toán với hai tham số g, b tương ứng với set đồ hiện tại và ngân quỹ hiện có. Với hai tham số cần quan tâm như vậy nên chúng ta kẻ một bảng hai chiều, tạm gọi là reachable kích thước 20 x 201. Ô reachable[g][b] sẽ lưu giá trị trạng thái (g, b) như mô tả trên.
Vào thời điểm ban đầu, tại dòng 0, tức g = 0, khi chọn lần lượt các model với giá 6, 4, 8, ngân quỹ còn lại sẽ tương ứng là 14, 16, 12 nên những ô tại các cột này được bật thành true.
Bước thứ 2, g =1, tương ứng với các ngân quỹ còn lại ở dòng 1, chúng ta chọn các món đồ cho set thứ 2 có giá 5, 10. Ngân quỹ tương ứng còn lại nằm ở 6 ô: 12 - 5 = 7, 12 -10 = 2, 14 - 5 = 9, ....
Quá trình lặp lại đến bước thứ 3, khi g2 có bốn món với giá 1 5 3 5, các ngân quỹ còn lại ở dòng 1 sẽ mua được các món tương ứng nếu đủ, ngân quỹ còn lại sẽ điền xuống dòng này.
Kết quả tối ưu tức nhiên nằm ở ô đầu tiên của dòng cuối reachable[2][1] ví ngân quỹ còn lại ít nhất nghĩa là chúng ta đã tiêu được số tiền nhiều nhất có thể mà vẫn nhỏ hơn M.
Nhìn vào bước thứ ba này chúng ta thấy rõ được ưu điểm của quy hoạch động so với backtracking. Rõ ràng có hai món hàng cùng giá là 5, như vậy sẽ có hai bài toán con cùng giá trị. Đồng thời nhiều ô khác nhau ở dòng trên khi trừ các giá trị khác nhau của set g2 này cũng cho ra cùng kết quả, nghĩa là cũng cho ra bài toán con giống nhau. Chẳng hạn với ngân quỹ 2 ta mua đồ có giá 1 sẽ bằng ngân quỹ 4 mua đồ giá 3 và cũng bằng ngân quỹ 6 mua đồ giá 5.
Code minh họa cho ý tưởng trên như sau:
const int MAX_gm = 30; // up to 20 garments at most and 20 models/garment
const int MAX_M = 210; // maximum budget is 200
int price[MAX_gm][MAX_gm]; // price[g (<= 20)][k (<= 20)]
bool reachable[MAX_gm][MAX_M]; // reachable table[g (<= 20)][money (<= 200)]
int main() {
int TC; scanf("%d", &TC);
while (TC--) {
int M, C; scanf("%d %d", &M, &C);
for (int g = 0; g < C; ++g) {
scanf("%d", &price[g][0]); // store k in price[g][0]
for (int k = 1; k <= price[g][0]; ++k)
scanf("%d", &price[g][k]);
}
memset(reachable, false, sizeof reachable); // clear everything
// initial values (base cases), using first garment g = 0
for (int k = 1; k <= price[0][0]; ++k)
if (M-price[0][k] >= 0)
reachable[0][M-price[0][k]] = true;
int money;
for (int g = 1; g < C; ++g) // for each garment
for (money = 0; money < M; money++) if (reachable[g-1][money])
for (int k = 1; k <= price[g][0]; ++k) if (money-price[g][k] >= 0)
reachable[g][money-price[g][k]] = true; // also reachable now
for (money = 0; money <= M && !reachable[C-1][money]; ++money);
for (money = 0; money <= M && !reachable[!cur][money]; ++money);
if (money == M+1) printf("no solution\n"); // last row has no on bit
else printf("%d\n", M-money);
}
return 0;
}
Nguồn code: Github --> Steven Halim - CPbook-code
Rất nhiều bài toán quy hoạch động giải theo hướng bottom có thể tận dụng lợi thể của Tabular bằng việc xem xét rằng giá trị các ô ở dòng dưới thực chất chỉ phụ thuộc vào dòng trước nó và giá trị tối ưu của bài toán luôn nằm ở dòng cuối của bảng, nên thay vì khai báo nguyên một mảng hai chiều với số dòng và cột tương tương ứng với giá trị hai tham số, ta chỉ cần một bảng có 2 dòng. Sau đó trong quá trình điền bảng, ta đảo thứ tự hai dòng này. Nghĩa là dùng dòng 0 tính dòng 1, sau đó đổi dòng 1 thàng 0 và dòng 0 thành 1.
Chẳng hạn với bài toán WeddingShopping, có thể thực hiện như sau:
//Tất cả các dòng khác giống hệt ở trên
// if using space saving technique
bool reachable[2][MAX_M]; // reachable table[ONLY TWO ROWS][money (<= 200)]
int money;
int cur = 1; // we start with this row
for (int g = 1; g < C; ++g) { // for each garment
memset(reachable[cur], false, sizeof reachable[cur]); // reset row
for (money = 0; money < M; ++money) if (reachable[!cur][money])
for (int k = 1; k <= price[g][0]; ++k) if (money-price[g][k] >= 0)
reachable[cur][money-price[g][k]] = true;
cur = 1-cur; // flip the two rows
}
for (money = 0; money <= M && !reachable[!cur][money]; ++money);
...
Nguồn code: Github --> Steven Hamlim - CPbook-code
Đến đây, chúng ta đã hình dung được phần nào cách triển khai quy hoạch động cho một bài toán theo hai hướng Top-Down và Bottom-Up. Cả hai đều dùng bảng để lưu giá trị bài toán con nhưng có một chút khác biệt. Trong khi bảng Memo trong Top-Down chỉ tính những bài toán con cần thiết trong quá trình đệ quy xuống thì Tabular của Bottom up tính hết các bài toán cơ sở rồi theo đó tính tiếp các bài toán lớn hơn theo thứ tự Topo. Cả hai đều có những ưu, khuyết riêng, tùy theo bài toán và tùy sở trường của mình, bạn có thể lựa chọn cách triển khai phù hợp.
So sánh giữa TopDown và BottomUp
Hiển thị phương án tối ưu
Hiển thị phương án tối ưu
Cách 1. Truy vết trên bảng Tabular
Cách 1. Truy vết trên bảng Tabular
Đa số các bài toán quy hoạch động thường chỉ yêu cầu đưa ra kết quả tối ưu, tuy nhiên vẫn có một số bài toán yêu cầu đưa ra phương án. Phương pháp sử dụng phổ biến đến hiện tại thường là truy vết. Phương pháp này dùng chủ yếu trong hướng tiếp cần Bottom-up. Với các bài toán dùng mảng 1 chiều để tính toán, ta thường cần thêm một mảng nữa để lưu vết, và truy vết dựa trên mảng này. Đối với bài toán dùng mảng hai chiều, như bài toán WeddingShopping, ta truy vết trực tiếp từ bảng đó.
Ví dụ, quá trình truy vết cho bài toán trên được tiến hành như sau:
Kết quả tối ưu nằm tại ơ Reachable[2][1], ô này được suy ra từ ô Reachable[1][2] nên ta truy ngược về [1][2].
Ô Reachable[1][2] được suy ra từ ô Reachable[0][12] nên ta truy ngược về ô này.
Kết quả xuất ngược lại là: {8, 10, 1} tương ứng với quá trình truy: 20 - 12, 12 - 2, 2 - 1
Tuy nhiên, vẫn có một đáp án khác, nhìn vào hình trên chúng ta cũng thấy ô [2][1] cũng được suy ra từ [1][6], và [1][6] thì được suy ra từ [0][16]. Cho nên nghiệm thứ 2 của bài toán cũng có thể là: {4, 10, 5}
Cách 2. Xuất từ Memoization
Cách 2. Xuất từ Memoization
Khi được cài đặt theo hướng Top-Down, chúng ta không dùng Tabular như Bottom-up nên không thể truy theo cách trên. Tuy nhiên, lợi thể của Top-Down là kết quả bài toán con khi đệ quy xuống được lưu trong Memo Table, nên là chỉ cần xuất nó ra trong quá trình hồi quy lên lại.
Chúng ta sẽ viết thêm một hàm xuất, với danh sách tham số giống hệt hàm trạng thái, còn nội dung bên trong hàm là để xuất giá trị bài toán con.
Ví dụ, với cách Top-Down của bài WeddingShopping, ta viết hàm xuất như sau:
void print_dp(int g, b){
if((g==C) || (b <0) return; // Giống trường hợp cơ sở
for (int k =1; k <=price[g][0]; ++k) // tìm món đồ có giá k tối ưu
if( dp(g+1, b - price[g][k] ==memo[g][b]){ //Đay là món đồ tối ưu
printf("%d - ", price[g][k]);
print_dp(g+1, b - price[g][k]); //Đệ quy tiếp
break;
}
}
Nhiệm vụ 1. Viết hàm xuất kết quả bài toán tương ứng cho cả hai cách Top-Down và Bottom-Up
Nhiệm vụ 2. Cải tiến cả hai cách trên để xuất ra tất cả phương án tối ưu cho bài toán
Tóm tắt: Cho một dãy n số nguyên A, 0<=n<=2*10^4, xác định đoạn có tổng lớn nhất của A. Nói cách khác là tìm một đoạn [i..j] ⊂ [0..n-1] sao cho tổng các phần tử của A từ i đến j là lớn nhất.
Hướng tiếp cận 1 - O(n^3)
Một hướng tiếp cận tự nhiên, ta dùng hai vòng lặp chạy lồng vào nhau để duyệt tất cả các cặp (i, j) trong phạm vi --> O(n^2). Trong mỗi cặp (i, j) đó dùng một vòng lặp tính sum --> RSQ(i, j) tốn thêm O(n), lấy max trong quá trình chạy tính tổng.
Hướng tiếp cận 2 - O(n^2)
Ta có thể tính trước mảng prefix_sum A[i] +=A[i-1], như vậy A[i] chứa tổng các số nguyên từ 0 đến i. Sau đó ta có thể RSQ(i, j) trong O(1): RSQ(0, j) = A[j] và RSQ(i, j) = A[j] - A[i -1]. Giải thuật O(n^2) này vẫn chưa thể full test được bài này khi giới hạn n <= 2*10^4.
Hướng tiếp cận O(n)
Hướng tiếp cận này dựa vào ý tưởng chính của Jay Kandane's. Trong đó, ông dùng một biến max_ending_here để lưu tổng lớn nhất cho đến chỉ số hiện tại và một biến max_so_far để lưu tổng lớn nhất tìm được cho đến thời điểm hiện tại. Mỗi khi có một số dương được cộng thêm vào max_ending_here thì ta so nó với max_so_far và cập nhật lại max_so_far nếu nó lớn hơn. Ý tưởng có thể được mô tả bằng mã giả như sau:
Khởi tạo:
max_so_far = INT_MIN
max_ending_here = 0
Duyệt qua từng phần tử mảng:
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_far
Code tham khảo:
int maxSubArraySum(int a[], int size)
{
int max_so_far = INT_MIN, max_ending_here = 0;
for (int i = 0; i < size; i++) {
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0) //Cần reset lại giá trị tổng vì bắt đầu từ 0 thì luôn tốt hơn
max_ending_here = 0; //bắt đầu từ một số âm
}
return max_so_far;
}
Nguồn code: GeeksforGeeks
In dãy con có tổng lớn nhất:
Để in được dãy con có tổng lớn nhất, ta phải duy trì một chỉ số bắt đầu start của maximum_sum_ending_here ở vị trí hiện tại, một khi maximum_sum_so_far được update thì ta sẽ update lại chỉ số bắt đầu và kết thúc.
Cách thực hiện như sau, thêm biến s, start và end vào đoạn chương trình maxSubArraySum trên:
Ban đầu khởi tạo cả s, start và end = 0.
Bên trong vòng lặp:
Mỗi lần update maximum_sum_so_far thì ta cũng update: start = s, end = i
Mỗi khi reset max_ending_here về 0 thì ta cũng update s = i+1 (vị trí bắt đầu mới)
Đoạn code được minh họa như sau:
void maxSubArraySum(int a[], int size)
{
int max_so_far = INT_MIN, max_ending_here = 0,
start = 0, end = 0, s = 0;
for (int i = 0; i < size; i++) {
max_ending_here += a[i];
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;
start = s;
end = i;
}
if (max_ending_here < 0) {
max_ending_here = 0;
s = i + 1;
}
}
cout << "Maximum contiguous sum is " << max_so_far
<< endl;
cout << "Starting index " << start << endl
<< "Ending index " << end << endl;
}
Nguồn code: GeeksforGeeks
Nhiệm vụ
Nhiệm vụ
Nhiệm vụ 3 - UVa 10684 - The jackpot
Nhiệm vụ 4 - Upcoder - Dãy con đơn điệu tăng dài nhất
Nhiệm vụ 5 - UVa 481 - What Goes Up
Nhiệm vụ 6 - Upcoder - Xâu con chung dài nhất
Nhiệm vụ 7 - Contest ngắn Practice DP 1 (Basic) ----- For ITs: Click here
Nhiệm vụ 8 - Contest ngắn Practice DP 2 (Basic too) -----For ITs: Click here
Nhiệm vụ 9 - Đội Tuyển - Luyện tập 3
Page updated
Google Sites
Report abuse