Lập trình Python

Thuật toán cái túi (Knapsack problem) trong Python

Posted on by Đỗ Thành
02
Th1
View: 272

Thuật toán “Cái túi” hay còn gọi là “Knapsack problem” trong tiếng Anh, là một bài toán kinh điển trong lĩnh vực tối ưu hóa và lý thuyết quyết định. Bài toán này thường được giải quyết bằng cách sử dụng các phương pháp lập trình động hoặc phương pháp tham lam.

Có hai biến thể chính của bài toán Knapsack:

  1. 0/1 Knapsack Problem: Bạn chỉ có thể chọn mỗi vật phẩm một lần. Câu hỏi đặt ra là làm thế nào để chọn các vật phẩm sao cho tổng giá trị là lớn nhất mà không vượt quá trọng lượng tối đa của túi.
  2. Fractional Knapsack Problem: Bạn có thể chọn một phần của mỗi vật phẩm, nghĩa là vật phẩm có thể được chia nhỏ. Mục tiêu là tối đa hóa tổng giá trị của túi dựa trên phần trăm của mỗi vật phẩm mà bạn chọn.

Code Python:

def knapsack(values, weights, W):
    N = len(values)
    K = [[0 for x in range(W + 1)] for x in range(N + 1)]

    for i in range(N + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif weights[i-1] <= w:
                K[i][w] = max(values[i-1] + K[i-1][w-weights[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]

    return K[N][W]

values = [60, 100, 120] 
weights = [10, 20, 30]  s
W = 50 

print("Maximum value in knapsack =", knapsack(values, weights, W))

Trong ví dụ trên, values và weights là hai danh sách chứa giá trị và trọng lượng của các vật phẩm. W là trọng lượng tối đa mà túi xách có thể chứa. Hàm knapsack sẽ trả về giá trị lớn nhất có thể đạt được mà không vượt quá trọng lượng tối đa này.

Đoạn code trên sử dụng phương pháp lập trình động để giải quyết bài toán. Cụ thể:

  1. Định nghĩa Hàm knapsack(values, weights, W):
    • values: Danh sách chứa giá trị của các vật phẩm.
    • weights: Danh sách chứa trọng lượng của các vật phẩm.
    • W: Trọng lượng tối đa mà túi xách có thể chứa.
  2. Tạo Bảng K:
    • Bảng này có kích thước (N + 1) x (W + 1) với N là số lượng vật phẩm.
    • K[i][w] sẽ lưu trữ giá trị tối đa có thể chứa trong túi xách có trọng lượng tối đa w khi có i vật phẩm.
  3. Xây dựng Bảng K Theo Cách Từ Dưới Lên:
    • Duyệt qua từng vật phẩm (i) và từng trọng lượng từ 0 đến W.
    • Nếu không chọn vật phẩm i hoặc trọng lượng w bằng 0, giá trị tối đa là 0.
    • Nếu trọng lượng của vật phẩm i nhỏ hơn hoặc bằng w, chọn giá trị lớn nhất giữa việc không chọn và chọn vật phẩm i.
    • Nếu không, giữ nguyên giá trị từ trên xuống (không chọn vật phẩm i).
  4. Trả Về Giá Trị:
    • K[N][W] sẽ chứa giá trị tối đa có thể đạt được.
  5. Ví dụ Sử Dụng:
    • Các vật phẩm có giá trị [60, 100, 120] và trọng lượng [10, 20, 30].
    • Trọng lượng tối đa của túi xách là 50.
    • Kết quả sẽ được in ra: “Maximum value in knapsack = [giá trị]”.

Mã này sẽ tính toán cách chọn vật phẩm để tổng giá trị trong túi xách là lớn nhất mà tổng trọng lượng không vượt quá trọng lượng cho phép.

Đỗ Thành