THUẬT TOÁN QUY HOẠCH ĐỘNG

1. Khái niệm về phương pháp quy hoạch động:

Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức

là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của

một số hữu hạn các bài toán con.

Ðối với một số bài toán đệ quy, nguyên lý chia để trị (divide and conquer) thường

đóng vai trò chủ đạo trong việc thiết kế thuật toán. Ðể giải quyết một bài toán lớn, ta

chia nó thành nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập.

Trong phương án quy hoạch động, nguyên lý chia để trị càng được thể hiện rõ:

Khi không biết phải giải quyết những bài toán con nào, ta sẽ đi giải quyết toàn bộ các

bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại

theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn.

Ðó chính là điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy và

cũng là nội dung phương pháp quy hoạch động:

• Phép phân giải đệ quy bắt đầu từ bài toán lớn phân ra thành nhiều bài toán con

và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân ra tiếp

thành nhiều bài toán nhỏ hơn và lại đi giải các bài toán nhỏ hơn đó bất kể nó đã được

giải hay chưa.

• Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở)

để từ đó từng bước giải quyết nhưng bài toán lớn hơn, cho tới khi giải được bài toán lớn

nhất (bài toán ban đầu).

Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy 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

gọi là công thức truy hồi của quy hoạch động.

Tập các bài toán có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi là

cơ sở quy hoạch động.

Không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng gọi là

bảng phương án của quy hoạch động.

Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương pháp đó

có thỏa mãn những yêu cầu dưới đây không:

• Bài toán lớn phải phân rã được thành nhiều bài toán con, mà 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.

• Vì quy hoạch động là đi giải tất cả các bài toán con, nên nếu không đủ không

gian vật lý lưu trữ lời giải (bộ nhớ, đĩa, ...) để phối hợp chúng thì phương pháp quy

hoạch động cũng không thể thực hiện được.

• Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn

bước. Các bước cài đặt một chương trình sử dụng quy hoạch động:

• Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu các lời giải vào bảng

phương án.

• Dùng công thức truy hồi phối hợp những lời giải của các bài toán nhỏ đã lưu

trong bảng phương án để tìm lời giải của các bài toán lớn hơn rồi lưu chúng vào bảng

phương án. Cho tới khi bài toán ban đầu tìm được lời giải.

• Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.

Cho tới nay, vẫn chưa có một định lý nào cho biết một cách chính xác những bài

toán nào có thể giải quyết hiệu quả bằng quy hoạch động. Tuy nhiên để biết được bài

toán có thể giải bằng quy hoạch động hay không, ta có thể đặt câu hỏi:

1. “Một nghiệm tối ưu của bài toán lớn có phải là sự phối hợp các nghiệm tối ưu

của các bài toán con hay không?”

2. “Liệu có thể nào lưu trữ được nghiệm các bài toán con dưới một hình thức nào

đó để phối hợp tìm được ngiệm bài toán lớn?”.

2. Các bước cơ bản để giải một bài toán quy hoạch động:

Với mỗi bài toán ứng dụng giải thuật quy hoạch động, ta vẫn phải trả lời rõ ràng,

chính xác 6 câu hỏi:

Tên và ý nghĩa các biến phục vụ sơ đồ lặp,

Cách khai báo các biến đó,

Sơ đồ (công thức) lặp chuyển từ một bước sang bước tiếp theo,

Giá trị đầu của các biến tham gia tính lặp,

Tham số điều khiển lặp: thay đổi từ đâu đến đâu,

Kết quả: ở đâu và làm thế nào để dẫn xuất ra.

Các cách trả lời khác nhau sẽ dẫn đến những giải thuật khác nhau cả về cách thực

hiện lẫn độ phức tạp.

3. Cách tiếp cận và phương pháp triển khai

Để tiếp cận và triển khai thuật toán quy hoạch động trong Python, bạn có thể làm theo các

bước sau:

Bước 1: Xác định cấu trúc của bài toán quy hoạch động Trước khi triển khai thuật toán, bạn

cần xác định cấu trúc tổng quát của bài toán quy hoạch động. Điều này bao gồm xác định

các bước phải thực hiện và các thành phần cần thiết để tính toán kết quả tối ưu.

Bước 2: Xác định và khởi tạo bảng phương án (table) Trong thuật toán quy hoạch động,

bảng phương án (table) được sử dụng để lưu trữ các kết quả trung gian để tính toán các giá

trị tối ưu. Bạn cần xác định cách lưu trữ dữ liệu trong bảng phương án và khởi tạo nó trong

Python.

Thay n = 30 cho ta P 30 = 228922,97 đô la.

Ví dụ 2: (Xâu nhị phân)

Tìm công thức truy hồi và cho điều kiện đầu để tính số các xâu nhị phân độ dài n

và không có hai số 0 liên tiếp. Có bao nhiêu xâu nhị phân như thế có độ dài bằng 5?

Gọi Sn là số các xâu nhị phân độ dài n và không có hai số 0 liên tiếp.

Để nhận được công thức truy hồi cho {Sn}, ta có số các xâu nhị phân độ dài n và

không có hai số 0 liên tiếp bằng số các xâu nhị phân như thế kết thúc bằng số 1 cộng với

số các xâu như thế kết thúc bằng số 0. Giả sử n ≥ 3.

Các xâu nhị phân độ dài n, không có hai số 0 liên tiếp kết thúc bằng số 1 chính là xâu

nhị phân như thế, độ dài n - 1 và thêm số 1 vào cuối của chúng. Vậy chúng có tất cả là

Sn-1 xâu

Các xâu nhị phân độ dài n, không có hai số 0 liên tiếp và kết thúc bằng số 0, cần

phải có bit thứ n - 1 bằng 1, nếu không thì chúng có hai số 0 ở hai bit cuối cùng. Trong

trường hợp này chúng có tất cả là Sn-2.

Cuối cùng ta có được:

Sn = Sn-1 + Sn-2 với n ≥ 3.

Điều kiện đầu là S 1 = 2 và S 2 = 3.

Khi đó S 5 = S 4 + S 3 = S 3 + S 2 + S 3

\= 2(S 2 + S 1 ) + S 2 = 13

c. Các bước cài đặt chương trình QHĐ:

1. Giải tất cả các bài toán cơ sở (thường rất dễ) và lưu vào bảng phương án

2. Dùng công thức truy hồi để phối hợp lời giải của những bài toán nhỏ đã lưu

trong bảng phương án để tìm lời giải những bài toán lớn hơn và lưu lại. Lặp lại cho đến

khi bài toán ban đầu tìm được lời giải.

3. Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu

6. Ví dụ về các bài toán có thể giải bằng phương pháp quy hoạch động

6. Bài toán Tính N! GT

Ta có định nghĩa như sau: n! = nếu

Cho một số nguyên dương n (0  n  13).

Yêu cầu: Hãy tính n! bằng phương pháp quy hoạch động (lập bảng phương án).

Dữ liệu vào: Ghi trong file văn bản GT có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương n.

Dữ liệu ra: Ghi ra file văn bản GT theo cấu trúc như sau:

• Dòng 1: Ghi giá trị tính được của n!

Ví dụ:

GT GT

3 6

Thuật toán:

Gọi GT[i] là giá trị của i! (0  i  13)

Ta có công thức quy hoạch động như sau:

GT[i] = GT[i-1]*i

Như vậy, việc tính n! sẽ được thực hiện bằng vòng lặp:

GT[0]=

For i in range(1,n+1)

GT[i] = GT[i-1]*i

Kết quả: giá trị của n! nằm trong phần tử GT[n].

6. Bài toán Tính dãy Fibonaci FIBO

Ta có định nghĩa như sau: F(n) = nếu

Cho một số nguyên dương n (0  n  50).

Yêu cầu: Hãy tính F(n) bằng phương pháp quy hoạch động (lập bảng phương án).

Dữ liệu vào: Ghi trong file văn bản FIBO có cấu trúc như sau:

- Dòng 1: Ghi số nguyên dương n.

Dữ liệu ra: Ghi ra file văn bản FIBO theo cấu trúc như sau:

- Dòng 1: Ghi giá trị tính được của F(n).

Ví dụ:

FIBO FIBO

5 8

Thuật toán:

Gọi F[i] là giá trị Fibonaci của fi (0  i  50).

Ta có công thức quy hoạch động như sau:

F[i] := F[i-1] + F[i-2];

Như vậy, việc tính fn được thực hiện bằng vòng lặp:

def fib(n):

dp = [0] * (n + 1)

dp[1] = 1

for i in range(2, n + 1):

dp[i] = dp[i - 1] + dp[i - 2]

return dp[n]

Kết quả: giá trị fn nằm trong F[n].

6. Bài toán Tìm dãy con tăng dài nhất (Longest Increasing Subsequence)

Cho dãy số A gồm n phần tử a1, a2,..., aN với ;n≤

6

); hãy xác đ ịnh dãy con tăng dài

nhất của d ãy số đ ã cho?

Input:

 Dòng đầu tiên chứa số nguyên dương n (1≤n≤10 6 ).

 Dòng thứ hai chứa n số nguyên dươnga 1 ,a 2 ,...,an (1≤ai≤10 9 ) phân tách nhau

bởi dấu cách - các phần tử của dãy số.

Output:

dp = [0] * (n + 1)

end_pos = [0] * (n + 1)

trace = [0] * (n + 1)

res = 1

end_pos[1] = 1

for i in range(1, n + 1):

# Tìm kiếm nhị phân đô ̣ dài p tốt nhất để ghép a[i] vào phía sau

# dãy con tăng dài nhất kết thúc tại a[end_pos[p]].

p = binary_searching(res, a, end_pos, a[i])

k = p + 1

# Câ ̣p nhâ ̣t đô ̣ dài dãy con tăng dài nhất hiê ̣n tại.

# Luôn giữ cho phần tử kết thúc của các dãy con tăng là nhỏ nhất có thể.

if k > res:

res = k

end_pos[k] = i

elif a[end_pos[k]] > a[i]:

end_pos[k] = i

# Câ ̣p nhâ ̣t các kết quả ở vị trí i.

dp[i] = k

trace[i] = end_pos[p]

print_result(n, a, dp, trace)

if name == &

039;main&

039;:

n = int(input())

a = [0] * (n + 1)

for i in range(1, n + 1):

a[i] = int(input())

solution(n, a)

Code tham khảo 2:

1 2 3 4 5 6 7 8 9

10

11

def longest_increasing_subsequence(nums):n = len(nums)lengths = [ 1 ] * nfor i in range( 1 , n):for j in range(i):if nums[i] > nums[j]:lengths[i] = max(lengths[i], lengths[j] + 1 )return max(lengths)l=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]print(longest_increasing_subsequence(l))

6 Bài toán Tìm tổng con lớn nhất (Maximum Subarray Sum)

Ví dụ, với mảng số nguyên [−2, 1, −3, 4, −1, 2, 1, −5, 4], ta có thể tìm được mảng con liên

tiếp có tổng lớn nhất là [4, −1, 2, 1], có tổng bằng 6.

1 2 3 4 5 6

def maximum_subarray_sum(nums):n = len(nums)max_sum = nums[ 0 ]current_sum = nums[ 0 ]for i in range( 1 , n):current_sum = max(nums[i], current_sum + nums[i])

7

8

9

10

max_sum = max(max_sum, current_sum)return max_sumlis= [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]print(maximum_subarray_sum(lis))

6 Bài toán kinh điển với đồng xu

Đây là một ví dụ rất kinh điển khi học về quy hoạch động. Có thể có nhiều cách

phát biểu khác nhau nhưng về cơ bản, nội dung của nó sẽ tương tự như sau.

Giả sử chúng ta có n đồng xu nặng lần lượt là W1, W2, ..., Wn, và bài toán đặt ra

là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị S. Tất

nhiên, số lượng đồng xu là không giới hạn.

Với bài toán này, chúng ta cần xây dựng và giải các bài toán con gối nhau. Với ví

dụ của chúng ta, mỗi bài toán con dp(P) với P <= S là bài toán tìm số đồng xu nhỏ nhất

để khối lượng của chúng là P. và dp(P) = k chính là số lượng đồng xu nhỏ nhất đó.

Chúng ta sẽ áp dụng phương pháp quy hoạch động bằng cách bắt đầu từ bài toán

con dp(0) sau đó tiếp tục với các bài toán con lớn hơn. Lời giải của các bài toán con sẽ

được xây dựng lần lượt cho đến chúng ta xây dựng đến bài toán dp(S) và đó chính là kết

quả của bài toán lớn. Một điều cần lưu ý với kỹ thuật này là bài toán con tiếp theo sẽ

không thể giải được nếu chúng ta chưa giải bài toán con trước đó.

Cuố i cùng là ph ầ n khó nh ấ t củ a mọi bà i toá n quy hoạch động, đó là trả lời câu

hỏi: c ấ u trúc con tố i ưu củ a bà i toá n nà y ở đâu. Hay nói một cá ch khá c, là m thế nà o để

từ những bà i toá n nhỏ hơn có thể tổ hợp ra lời giải cho bà i toá n lớn. Với ví dụ kinh

điển này, mọi thứ sẽ tương đối đơn giản, nhưng với những bài toán phức tạp hơn, chúng

ta cần suy nghĩ và tính toán nhiều hơn.

Quay trở lại với bài toán của chúng ta. Giả sử P là tổng khối lượng của các đồng

xu nặng lần lượt là V1, V2, ..., Vj. Để có được khối lượng P, chúng ta cần thêm vài

đúng 1 đồng xu nặng U vào khối lượng Q sao cho Q + U = P. Tất nhiên, bài toán con

dp(Q) chúng ta đã có lời giải nên chúng ta sẽ biết được cần bao nhiêu đồng xu cho

dp(P). Và vì có nhiều đồng xu U (nhiều nhưng hữu hạn) nên chúng ta có thể cần đến

nhiều bài toán con trước đó, và dp(p) là giá trị nhỏ nhất sau khi tổng hợp những bài toán

con đó.

Ví dụ với n = 3, S = 11, W = [1, 3, 5].

Bắt đầu với bài toán con 0 ta có dp(0) = 0

Với bài toán con 1, có 1 đồng xu (nặng 1) có thể thêm vào từ 0 đồng xu nào cả.

Vậy dp(1) = dp(0) + 1 = 1.

Với bài toán con 2, cũng chỉ có 1 đồng xu (nặng 1) có thể thêm vào từ 1 đồng xu.

Vậy dp(2) = dp(1) + 1 = 2.

Với bài toán con 3, chúng ta có thể thêm 1 đồng xu 3 vào 0 đồng xu hoặc thêm 1

đồng xu 1 vào 2 đồng xu. Rõ ràng là cách đầu tiên cho kết quả nhỏ hơn. Vậy dp(3) =

min(dp(2) + 1, dp(0) + 1) = min(3, 1) = 1

...

Cứ tiếp tục như vậy cho đến bài toán S chính là đáp án chúng ta cần tìm.

Về mặt cài đặt, quy hoạch động thường lưu kết quả vào một mảng. Trong ví dụ

của chúng ta, mảng dp[0.] sẽ lưu kết quả cho từng bài toán con. Nói cách khác, dp[P]

\= k nghĩa là cần ít nhất k đồng xu để có khối lượng là P Toàn bộ mảng này sẽ được tính

bằng vòng lặp. Đoạn code sau mô tả toàn bộ quá trình này.

n, S = map(int, input().split())

for j, x2 in enumerate(s2, 1):

if x1 == x2:

t[i][j] = t[i - 1][j - 1] + 1

else:

t[i][j] = max(t[i][j - 1], t[i - 1][j])

print(t[-1][-1])

# Kết quả khi giải các bài toán con như bảng sau:

null

# S| t e z c a t l i p o c a

# T ji| 0 1 2 3 4 5 6 7 8 9 10 11 12

# +------

# 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0

# q 1 | 0 0 0 0 0 0 0 0 0 0 0 0 0

# u 2 | 0 0 0 0 0 0 0 0 0 0 0 0 0

# e 3 | 0 0 1 1 1 1 1 1 1 1 1 1 1

# t 4 | 0 1 1 1 1 1 2 2 2 2 2 2 2

# z 5 | 0 1 1 2 2 2 2 2 2 2 2 2 2

# a 6 | 0 1 1 2 2 3 3 3 3 3 3 3 3

# l 7 | 0 1 1 2 2 3 3 4 4 4 4 4 4

# c 8 | 0 1 1 2 3 3 3 4 4 4 4 5 5

# o 9 | 0 1 1 2 3 3 3 4 4 4 5 5 5

# a 10| 0 1 1 2 3 4 4 4 4 4 5 5 6

# t 11| 0 1 1 2 3 4 5 5 5 5 5 5 6

# l 12| 0 1 1 2 3 4 5 6 6 6 6 6 6

BÀI TẬP

1. Chia kẹo

Có n gói kẹo lần lượt chứa a 1 , a 2 , .., an viên kẹo. Bạn thứ nhất được chia các gói kẹo từ 1 đến i(1  i < n), bạn thứ hai được chia các gói kẹo từ i+1 đến n. Viết chương trình chia n gói kẹo đó chohai bạn sao cho chênh lệch giữa số viên kẹo nhận được của hai bạn là nhỏ nhất (yêu cầu không bóccác gói kẹo).

Dữ liệu vào từ file: bai3

Gồm 2 dòng:+ Dòng thứ nhất chứa số tự nhiên n (1< n  100).+ Dòng thứ hai gồm n số từ a 1 , a 2 , .., an (1< ai  109 ; i = 1,2,3,...,n) mỗi số cách nhau một kýtự khoảng trắng.

Kết quả ra file: bai3

Gồm nhiều dòng:Mỗi phương án được ghi trên hai dòng liên tiếp: Dòng thứ nhất ghi số kẹo có trong từng gói từ1 đến i; dòng thứ hai ghi số kẹo có trong từng gói từ I + 1 đến n, mỗi số cách nhau một khoảng trắng.Ví dụ:

bai3 bai3 Giải thích

4

3 6 8 5

3 6

8 5

Độ chênh lệch nhỏ nhất là 4

5

3 4 6 2 5

3 4

6 2 5

Độ chênh lệch nhỏ nhất là 6

3 4 6

2 5

2. Dãy tăng

Cho dãy số C[n] với n < 100 gồm các hạng tử C[i] là các số nguyên có giá trị trong khoảng -10000

Dữ liệu vào từ file: DAYTANG

• Dòng 1: Ghi số n.
• Dòng 2: Ghi các phần tử của dãy số, mỗi số viết cách nhau ít nhất một khoảng

trắng.

Kết quả ra file: DAYTANG

• Dòng 1: In ra số phần tử của dãy con tìm được.
• Dòng 2: In ra các phần tử của dãy con tìm được, mỗi số viết cách nhau ít nhất

một khoảng trắng.

Ví dụ:

DAYTANG DAYTANG

13

3 4 -1 2 13 7 8 9 -5 -2 3 10 9

4

-5 -2 3 10

11

2 13 7 8 9 -5 21 3 9 10 -

3

3 9 10

3. Tính lãi suất

Sau một đơn vị thời gian (kỳ hạn), tiền lãi được gộp và o vố n và được tính lãi,

cá ch tính lãi nà y được gọi l à Lãi kép (hay lãi cộng dồn).

Chẳng hạn: Khi gửi tiết kiệm số tiền gốc là 100 (triệu đồng) vào ngân hàng với lãi suất 6%một năm thì sau một năm, ta nhận được số tiền cả gốc và lãi là:100 + 100*6% = 106 (triệu đồng)Toàn bộ số tiền 106 (triệu đồng) được gọi là tiền gốc để tính lãi cho năm tiếp theo (lãi suấtcho các năm tiếp theo không thay đổi).

1 5

2 3

4 4

5

Thuật toán:

Gọi A[i] là giá trị của phần tử thứ i trong dãy số a 1 , a 2 , ..., an.

Gọi T[i] là tổng giá trị các phần tử a 1 , a 2 , ..., ai (1  i  n).

Ta có công thức quy hoạch động để tính T[i] như sau:

T[i] = T[i - 1] + A[i]

Như vậy, việc tính T[n] được thực hiện bằng vòng lặp:

T[0] = 0

For i in range (1, n+1):

T[i] = T[i - 1] + A[i]

Kết quả: Tổng các phần tử liên tiếp từ ap đến aq được tính theo công thức:

Sum = A[q] - A[p-1]