NỘI DUNG
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.
Bước 3: Xác định công thức đệ quy (recurrence relation) Thuật toán quy hoạch động thường dựa trên công thức đệ quy để tính toán giá trị tối ưu. Bạn cần xác định công thức đệ quy cho bài toán cụ thể của mình.
Bước 4: Triển khai thuật toán quy hoạch động bằng Python Sau khi đã xác định cấu trúc bài toán, bảng phương án, và công thức đệ quy, bạn có thể triển khai thuật toán quy hoạch động bằng Python.
Bước 5: Thử nghiệm và tinh chỉnh Sau khi triển khai thuật toán, bạn nên thử nghiệm với các bộ dữ liệu khác nhau để đảm bảo rằng thuật toán hoạt động chính xác và hiệu quả. Nếu cần thiết, bạn có thể tinh chỉnh và cải thiện hiệu suất của thuật toán bằng cách tối ưu hóa các phần của mã.
Lưu ý rằng đây chỉ là một hướng dẫn cơ bản để tiếp cận và triển khai thuật toán quy hoạch động trong Python. Cách tiếp cận và phương pháp triển khai có thể khác nhau tùy thuộc vào bài toán cụ thể bạn đang giải quyết.
Các bài toán áp dụng thuật toán quy hoạch động trong Python
Bài toán Tìm dãy con tăng dài nhất (Longest Increasing Subsequence)
def longest_increasing_subsequence(nums):
n = len(nums)
lengths = [1] * n
for 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)
Bài toán Tìm tổng con lớn nhất (Maximum Subarray Sum)
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])
max_sum = max(max_sum, current_sum)
return max_sum
Bài toán Tìm số cách chia tiền (Coin Change)
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Bài toán Tìm đường đi ngắn nhất trong đồ thị (Shortest Path in a Graph)
import sys
def shortest_path(graph, start, end):
n = len(graph)
distances = [sys.maxsize] * n
distances[start] = 0
for _ in range(n - 1):
for u in range(n):
for v in range(n):
if graph[u][v] != 0:
distances[v] = min(distances[v], distances[u] + graph[u][v])
return distances[end]
Bài toán Cắt que tính điểm tối ưu (Cutting Rod Problem)
def max_profit(prices, length):
n = len(prices)
dp = [0] * (length + 1)
for i in range(1, length + 1):
for j in range(1, min(i, n) + 1):
dp[i] = max(dp[i], prices[j] + dp[i - j])
return dp[length]
Bài toán Bắt chuột (Mouse and Cheese Problem)
def max_cheese(matrix):
m = len(matrix)
n = len(matrix[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
dp[i][j] = matrix[i][j]
elif i == 0:
dp[i][j] = matrix[i][j] + dp[i][j - 1]
elif j == 0:
dp[i][j] = matrix[i][j] + dp[i - 1][j]
else:
dp[i][j] = matrix[i][j] + max(dp[i - 1][j], dp[i][j - 1])
return dp[m - 1][n - 1]
Bài toán Xếp hình chữ nhật (Box Stacking Problem)
def max_height(boxes):
rotated_boxes = []
for box in boxes:
rotated_boxes.append((box[0], box[1], box[2]))
rotated_boxes.append((box[1], box[0], box[2]))
rotated_boxes.append((box[2], box[0], box[1]))
rotated_boxes.sort(key=lambda x: x[0] * x[1], reverse=True)
n = len(rotated_boxes)
heights = [0] * n
for i in range(n):
heights[i] = rotated_boxes[i][2]
for j in range(i):
if rotated_boxes[j][0] > rotated_boxes[i][0] and rotated_boxes[j][1] > rotated_boxes[i][1]:
heights[i] = max(heights[i], heights[j] + rotated_boxes[i][2])
return max(heights)
Bài toán Tìm số lớn nhất không chứa chữ số 9 (Largest Number Without 9)
def largest_number_without_nine(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
if '9' not in str(i):
dp[i] = dp[i - 1] + 1
else:
dp[i] = dp[i - 1]
return dp[n]
Bài toán Sắp xếp công việc (Job Scheduling Problem)
def max_profit(jobs):
jobs.sort(key=lambda x: x[1])
n = len(jobs)
dp = [0] * n
for i in range(1, n):
dp[i] = max(jobs[i][2], dp[i - 1])
for j in range(i):
if jobs[j][1] <= jobs[i][0]:
dp[i] = max(dp[i], jobs[i][2] + dp[j])
return dp[n - 1]
Bài toán Đặt chỗ xe (Parking Lot Problem)
def min_cost(parking_lot):
m = len(parking_lot)
n = len(parking_lot[0])
dp = [[float('inf')] * n for _ in range(m)]
dp[0][0] = parking_lot[0][0]
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + parking_lot[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j - 1] + parking_lot[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = parking_lot[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[m - 1][n - 1]
Bài toán Xây tường (Building Walls Problem)
def min_cost(walls):
n = len(walls)
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
for j in range(i):
dp[i] = min(dp[i], dp[j] + abs(walls[i] - walls[j]))
return dp[n - 1]
Bài toán Xếp hình vuông (Square Stacking Problem)
def max_height(squares):
squares.sort(key=lambda x: x[0], reverse=True)
n = len(squares)
heights = [0] * n
for i in range(n):
heights[i] = squares[i][1]
for j in range(i):
if squares[j][0] > squares[i][0]:
heights[i] = max(heights[i], heights[j] + squares[i][1])
return max(heights)
Bài toán Chia mảng thành hai phần có tổng gần nhau nhất (Partition Array into Two Parts with Equal Sum)
def can_partition(nums):
total_sum = sum(nums)
if total_sum % 2 != 0:
return False
target_sum = total_sum // 2
n = len(nums)
dp = [[False] * (target_sum + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True
for i in range(1, n + 1):
for j in range(1, target_sum + 1):
if nums[i - 1] <= j:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
else:
dp[i][j] = dp[i - 1][j]
return dp[n][target_sum]
Bài toán Tìm đường đi ngắn nhất trong ma trận (Shortest Path in a Matrix)
def shortest_path(matrix):
m = len(matrix)
n = len(matrix[0])
dp = [[float('inf')] * n for _ in range(m)]
dp[0][0] = matrix[0][0]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for i in range(m):
for j in range(n):
for dx, dy in directions:
x, y = i + dx, j + dy
if 0 <= x < m and 0 <= y < n:
dp[x][y] = min(dp[x][y], dp[i][j] + matrix[x][y])
return dp[m - 1][n - 1]