Quy hoạch động (dynamic programming) giống với chia để trị, chia bài toán thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu. Tuy nhiên khác với chia để trị, thay vì sử dụng đệ quy, quy hoạch động lưu trữ lời giải của các bài toán con đã giải. Do vậy, nếu sau này ta cần giải lại chính bài toán đó, ta có thể lấy và sử dụng kết quả đã được tính toán.
1. Bài toán đổi tiền
def RecursiveChange(money, coins):
if money == 0:
return 0
MinNumCoins = float('inf')
for i in range(len(coins)):
if money >= coins[i]:
NumCoins = RecursiveChange(money - coins[i], coins)
if NumCoins + 1 < MinNumCoins:
MinNumCoins = NumCoins + 1
return MinNumCoins
print(RecursiveChange(9, [6, 5, 1]))Mô tả cây đệ quy mathcha.io
b. Sử dụng quy hoạch động bottom-up
def DPChange(money, coins):
MinNumCoins = [None]*(money + 1)
MinNumCoins[0] = 0
for m in range(1, money + 1):
MinNumCoins[m] = float('inf')
for i in range(len(coins)):
if m >= coins[i]:
NumCoins = MinNumCoins[m - coins[i]] + 1
if NumCoins < MinNumCoins[m]:
MinNumCoins[m] = NumCoins
return MinNumCoins[money]
print(DPChange(9, [6, 5, 1]))2. Khoảng cách chỉnh sửa
Cho hai chuỗi ký tự, tìm số lượng tối thiểu các thao tác (chèn, xóa và thay thế các ký hiệu) để biến đổi chuỗi này thành chuỗi kia.
a, Tính toán khoảng cách chỉnh sửa
def edit_distance(str_1, str_2, n, m):
if n == 0:
return m
if m == 0:
return n
if str_1[n-1] == str_2[m-1]:
return edit_distance(str_1, str_2, n-1, m-1)
return 1 + min(edit_distance(str_1, str_2, n, m-1),\
edit_distance(str_1, str_2, n-1, m),\
edit_distance(str_1, str_2, n-1, m-1))
str_1 = 'dis'
str_2 = 'edi'
print(edit_distance(str_1, str_2, len(str_1), len(str_2)))Độ phức tạp về thời gian của thuật toán là
$\begin{aligned}T(n)&=\begin{cases} 1& \text{nếu } n=0 \\ 3T(n-1)+C & \text{còn lại} \end{cases}\\ & = 3^n+nc=O(3^n) \end{aligned}$
Ta để ý thấy sau khi đệ quy sẽ sẽ có những bài toán đã lặp lại cho nên ta tạo ra một bộ nhớ phụ để lưu lại kết quả đã tính toán trước đó, nếu gặp bài toán tương tự chỉ việc lấy đáp án ra sử dụng.
Code python
def edit_distance(str1, str2, n, m):
dp = [[-1 for j in range(m+1)] for i in range(n+1)]
if n == 0:return m
if m == 0:return n
if dp[n][m] != -1:return dp[n][m]
if str1[n-1] == str2[m-1]:
if dp[n-1][m-1] == -1:
dp[n][m] = edit_distance(str1, str2, n-1, m-1)
return dp[n][m]
else:
dp[n][m] = dp[n-1][m-1]
return dp[n][m]
else:
if dp[n][m-1] != -1:m1 = dp[n][m-1]
else:m1 = edit_distance(str1, str2, n, m-1)
if dp[n-1][m] != -1:m2 = dp[n-1][m]
else:m2 = edit_distance(str1, str2, n-1, m)
if dp[n-1][m-1] != -1:m3 = dp[n-1][m-1]
else:m3 = edit_distance(str1, str2, n-1, m-1)
dp[n][m] = 1 + min(m1, m2, m3)
return dp[n][m]
str1, str2 = "dis", "edi"
n, m = len(str1), len(str2)
print(edit_distance(str1, str2, n, m))Độ phức tạp trên là quá lớn cho nên ta xem xét hướng tiếp cận bottom-up (Từ dưới lên) như sau
.gif)
def edit_string(str_1, str_2, n, m):
dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
for j in range(m+1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif str_1[i-1] == str_2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
return dp[n][m]
str_2 = 'dis'
str_1 = 'edi'
print(edit_string(str_1, str_2, len(str_1), len(str_2))).gif)
def edit_distance(str1, str2, n, m):
ED = [1*j for j in range(m+1)]
for i in range(1,n+1):
left,dag = i, i-1
for j in range(1,m+1):
if str1[i-1] == str2[j-1]:
curr = min(ED[j]+1, left+1, dag)
else: curr = min(ED[j]+1, left+1, dag+1)
left, dag, ED[j] = curr, ED[j], curr
return ED[m]
str1 = "dis"
str2 = "edi"
print(edit_distance(str1, str2, len(str1), len(str2)))3. Bài toán cái túi
a, Bài toán cái túi với điều kiện lặp
Phân tích
def kanapsack(W, w_i, v_i):
value = [None]*(W+1)
value[0] = 0
for w in range(1,W+1):
value[w] = 0
for i in range(len(w_i)):
if w_i[i] <= w:
val = value[w - w_i[i]] + v_i[i]
if val > value[w]:
value[w] = val
return value[W]
print(kanapsack(10,[6,3,4,2],[30,14,16,9]))b, Bài toán cái túi với điều kiện không lặp
Gọi $0 \leq w \leq W$ và $0 \leq i \leq n$, $value(w,i)$ là giá trị lớn nhất của knapsack, khi đó $value(w,i)=max\left \{value(w-w_i,i-1)+v_i,value(w,i-1) \right \}$Code python
def knapsack(W,w_i,v_i):
value = [[None for j in range(W+1)] for i in range(len(w_i)+1)]
for j in range(W+1):
value[0][j] = 0
for i in range(1,len(w_i)+1):
value[i][0] = 0
for i in range(1,len(w_i)+1):
for w in range(1,W+1):
value[i][w] = value[i-1][w]
if w_i[i-1] <= w:
val = value[i-1][w-w_i[i-1]] + v_i[i-1]
if val > value[i][w]:
value[i][w] = val
return value[len(w_i)][W]
print(knapsack(10,[6,3,4,2],[30,14,16,9]))
