Viết thuật toán động

6.1 Các bước cơ bản khi phát triển thuật toán động.

Các bước cơ bản khi phát triển thuật toán động

1. Xác định bài toán con:

Chia nhỏ bài toán thành các bài toán con nhỏ hơn, có thể giải quyết độc lập với nhau. Những bài toán con này cần phải có sự chồng lấn để có thể sử dụng các kết quả tính toán trước đó.

2. Xác định trạng thái:

Xác định tất cả các trạng thái có thể xuất hiện khi giải quyết bài toán. Trạng thái phải mô tả tất cả thông tin cần thiết để chuyển từ một bước sang bước tiếp theo.

3. Đặt công thức đệ quy:

Xác định cách giải bài toán cho trạng thái hiện tại phụ thuộc vào giải pháp cho các trạng thái trước đó. Công thức này phải biểu thị cách có thể đạt được giải pháp tối ưu, sử dụng giải pháp cho các bài toán con.

4. Xác định trường hợp cơ bản:

Xác định các trường hợp cơ bản mà giải pháp cho bài toán đã biết trực tiếp mà không cần thực hiện thêm tính toán.

5. Điền bảng:

Tạo bảng (thường là mảng hoặc ma trận) để lưu trữ giải pháp cho tất cả các bài toán con. Sử dụng công thức đệ quy và các trường hợp cơ bản để điền bảng từ dưới lên hoặc từ trên xuống.

6. Tối ưu hóa (Memoization):

Nếu sử dụng phương pháp đệ quy, thêm memoization để lưu trữ kết quả của các bài toán con và tránh tính toán lại chúng.

Độ phức tạp thời gian và không gian của thuật toán động

Độ phức tạp thời gian:

• Độ phức tạp thời gian của thuật toán động thường được biểu thị qua số lượng bài toán con và thời gian cần thiết để tính toán mỗi bài toán con.
• Trong hầu hết các trường hợp, độ phức tạp thời gian là O(n) hoặc O(n^2), nơi n là kích thước dữ liệu đầu vào.

Độ phức tạp không gian:

• Độ phức tạp không gian phụ thuộc vào số lượng trạng thái cần lưu trữ.
• Trong một số trường hợp có thể giảm độ phức tạp không gian bằng cách tối ưu hóa như giảm dung lượng bộ nhớ xuống O(n) hoặc O(1).

6.2 Bài toán ba lô.

Bài toán ba lô là vấn đề kinh điển của tối ưu hóa tổ hợp, thường xuất hiện trong nhiều lĩnh vực, bao gồm tin học, kinh tế và quản lý logistics. Mục tiêu chính của bài toán là sử dụng hiệu quả nhất các nguồn lực có hạn.

Mô tả bài toán ba lô

Có một cái ba lô có thể chịu tải trọng xác định W. Ngoài ra có n vật phẩm, mỗi vật đều có trọng lượng wt[i] và giá trị val[i]. Cần xác định những vật phẩm nào cần lấy để tối đa hóa tổng giá trị của các vật phẩm trong ba lô, không vượt quá tải trọng của nó.

Các loại bài toán ba lô

1. Bài toán ba lô 0/1 (0/1 Knapsack Problem):

Mỗi vật phẩm có thể được lấy hoặc không (không thể lấy một phần).

2. Bài toán ba lô chia phần (Fractional Knapsack Problem):

Mỗi vật phẩm có thể được chia và lấy bất kỳ phần nào.

3. Bài toán ba lô đa dạng (Multiple Knapsack Problem):

Có nhiều ba lô với các giới hạn trọng lượng khác nhau.

Mô phỏng bài toán ba lô 0/1 theo lý thuyết thuật toán:

Công thức đệ quy:

Đối với mỗi vật phẩm i và cho mỗi trọng lượng khả dĩ w (từ 0 đến W), giải pháp tối ưu có thể được biểu diễn như sau:

• Nếu vật phẩm i không được cho vào ba lô, giá trị tối ưu bằng giá trị tối ưu cho i - 1 vật phẩm và trọng lượng w.
• Nếu vật phẩm i được chọn cho vào ba lô, giá trị tối ưu bằng giá trị của vật phẩm cộng với giá trị tối ưu cho i − 1 vật phẩm và trọng lượng w − wt[i].

Độ phức tạp thời gian và không gian

Độ phức tạp thời gian:

Độ phức tạp thời gian của thuật toán này là O(nW) nơi n là số lượng vật phẩm, và W là dung lượng của ba lô. Điều này do cần phải điền vào bảng kích thước n × W.

Độ phức tạp không gian:

Độ phức tạp không gian cũng là O(nW), vì cần bảng để lưu trữ kết quả trung gian.

Ví dụ thực hiện bài toán ba lô 0/1

def knapsack(W, wt, val, n):
    # Tạo bảng để lưu trữ giá trị trung gian
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Điền bảng dp từ dưới lên
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# Ví dụ sử dụng
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Giá trị tối đa của ba lô: {knapsack(W, wt, val, n)}")
        

6.3 Bài toán đổi tiền xu.

Bài toán đổi tiền xu là một bài toán kinh điển của lập trình động, tìm cách xác định số lượng ít nhất các đồng xu hoặc số cách tạo ra một tổng số tiền nhất định từ một tập hợp các đồng xu có các mệnh giá cho trước. Bài toán này có hai biến thể chính:

Số lượng đồng xu ít nhất (Minimum Coin Change Problem):

Tìm số lượng đồng xu ít nhất để tạo ra tổng số tiền cho trước.

Số cách (Number of Ways to Make Change):

Tìm số cách khác nhau để tạo ra tổng số tiền cho trước từ tập hợp các đồng xu cho trước.

Biến thể 1. Số lượng đồng xu ít nhất

Đặt vấn đề

Cho:

• Một tập vô hạn các đồng xu có các mệnh giá nhất định.
• Tổng số tiền mục tiêu S.

Cần:

• Tìm số lượng ít nhất các đồng xu để tạo ra tổng số tiền S.

Giải pháp sử dụng lập trình động

Công thức đệ quy:

• Giả sử dp[i] đại diện cho số lượng ít nhất các đồng xu cần thiết để tạo ra tổng số tiền i.
• Với mỗi đồng xu c trong tập hợp đồng xu, nếu i ≥ c, thì: dp[i] = min(dp[i], dp[i − c] + 1)

Các trường hợp cơ bản:

• dp[0] = 0 (đối với tổng số tiền 0 thì cần 0 đồng xu).

Độ phức tạp thời gian và không gian:

• Độ phức tạp thời gian: O(n ⋅ S) nơi n là số lượng mệnh giá và S là tổng số tiền mục tiêu.
• Độ phức tạp không gian: O(S) vì cần mảng để lưu trữ số lượng ít nhất các đồng xu cho mỗi tổng từ 0 đến S.

Ví dụ thực hiện bằng Python

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# Ví dụ sử dụng
coins = [1, 2, 5]
S = 11
print(f"Số lượng đồng xu ít nhất cho số tiền {S}: {min_coins(coins, S)}")
        
        

Bài toán đổi tiền xu thể hiện tính linh hoạt của lập trình động. Nó được sử dụng để huấn luyện và nghiên cứu các kỹ thuật thuật toán, vì nó cho thấy cách có thể sử dụng công thức đệ quy và các trường hợp cơ bản để giải quyết các vấn đề hiệu quả