Bài toán ba lô 0-1 là một bài toán tối ưu hóa tổ hợp kinh điển. Nó được phát biểu như sau: cho một tập hợp các vật phẩm, mỗi vật phẩm có một trọng lượng và một giá trị nhất định. Với một chiếc ba lô có sức chứa tối đa là W, làm thế nào để chọn ra các vật phẩm sao cho tổng giá trị của chúng là lớn nhất mà không vượt quá sức chứa của ba lô. Tên gọi "0-1" xuất phát từ việc mỗi vật phẩm hoặc được chọn (1) hoặc không được chọn (0).

Chúng ta sẽ xem xét một ví dụ cụ thể để minh họa.

Ví dụ

Giả sử chúng ta có một chiếc ba lô với sức chứa tối đa là 12. Các vật phẩm có giá trị và trọng lượng tương ứng như sau:

• Vật phẩm 1: Giá trị = 100, Trọng lượng = 10
• Vật phẩm 2: Giá trị = 70, Trọng lượng = 4
• Vật phẩm 3: Giá trị = 50, Trọng lượng = 6
• Vật phẩm 4: Giá trị = 10, Trọng lượng = 12

Mục tiêu là tìm cách đặt các vật phẩm vào ba lô sao cho tổng giá trị đạt được là lớn nhất, không vượt quá 12 đơn vị trọng lượng. Trong trường hợp này, việc chọn vật phẩm 2 (trọng lượng 4, giá trị 70) và vật phẩm 3 (trọng lượng 6, giá trị 50) sẽ mang lại tổng giá trị là 120 với tổng trọng lượng là 10, là giải pháp tối ưu.

Phân tích và giải pháp đệ quy

Chúng ta có thể tiếp cận bài toán này bằng phương pháp đệ quy. Hãy xem xét vật phẩm cuối cùng (với chỉ số i). Có hai lựa chọn:

1. Chọn vật phẩm i: Nếu trọng lượng của vật phẩm i (weights[i]) không vượt quá sức chứa còn lại (w), chúng ta có thể chọn nó. Tổng giá trị lúc này sẽ là giá trị của vật phẩm i (values[i]) cộng với giá trị tối ưu thu được từ việc giải bài toán cho các vật phẩm còn lại (từ 0 đến i-1) với sức chứa còn lại là w - weights[i].
2. Không chọn vật phẩm i: Chúng ta bỏ qua vật phẩm i và tìm giải pháp tối ưu cho các vật phẩm còn lại (từ 0 đến i-1) với cùng sức chứa w.

Chúng ta sẽ chọn phương án mang lại giá trị cao hơn. Trường hợp cơ sở của đệ quy là khi không còn vật phẩm nào để xem xét (i < 0) hoặc sức chứa còn lại là 0 (w == 0), khi đó giá trị tối ưu là 0.

Dưới đây là cài đặt đệ quy cho hàm này:

values = [100, 70, 50, 10]
weights = [10, 4, 6, 12]
max_weight = 12

def solve_knapsack_recursive(index, current_weight):
    # Trường hợp cơ sở
    if index < 0 or current_weight == 0:
        return 0

    # Nếu trọng lượng vật phẩm hiện tại lớn hơn sức chứa còn lại
    if weights[index] > current_weight:
        return solve_knapsack_recursive(index - 1, current_weight)

    # Lựa chọn tốt nhất giữa việc chọn hoặc không chọn vật phẩm hiện tại
    value_if_included = values[index] + solve_knapsack_recursive(index - 1, current_weight - weights[index])
    value_if_excluded = solve_knapsack_recursive(index - 1, current_weight)

    return max(value_if_included, value_if_excluded)

# Gọi hàm với vật phẩm cuối cùng và sức chứa tối đa
result = solve_knapsack_recursive(len(values) - 1, max_weight)
print(result)

Quy hoạch động

Cách tiếp cận đệ quy ở trên có thể dẫn đến việc tính toán lặp lại nhiều trạng thái con. Quy hoạch động giúp tối ưu hóa điều này bằng cách lưu trữ kết quả của các trạng thái con đã được tính toán.

Chúng ta có thể định nghĩa một bảng dp, trong đó dp[i][w] biểu thị giá trị tối đa có thể đạt được khi xem xét i vật phẩm đầu tiên với sức chứa ba lô là w.

Công thức truy hồi như sau:

• Nếu trọng lượng của vật phẩm thứ i (item_weights[i]) lớn hơn sức chứa hiện tại w, thì dp[i][w] = dp[i-1][w] (không thể chọn vật phẩm i).
• Nếu trọng lượng của vật phẩm thứ i nhỏ hơn hoặc bằng w, thì dp[i][w] = max(dp[i-1][w], item_values[i] + dp[i-1][w - item_weights[i]]). Nghĩa là, chúng ta chọn giá trị lớn hơn giữa việc không chọn vật phẩm i hoặc chọn vật phẩm i.

Bảng dp sẽ có kích thước (n+1) x (W+1), trong đó n là số lượng vật phẩm và W là sức chứa tối đa của ba lô. Các giá trị ban đầu dp[0][w] và dp[i][0] đều bằng 0.

Cài đặt bằng Quy hoạch động

Chúng ta sẽ sử dụng một mảng 2 chiều để lưu trữ kết quả. Lưu ý rằng để thuận tiện cho việc lập chỉ mục, chúng ta thường thêm một vật phẩm giả có giá trị và trọng lượng bằng 0 vào đầu danh sách.

import numpy as np

def solve_knapsack_dp(item_values, item_weights, total_capacity, num_items):
    # Khởi tạo bảng DP với kích thước (num_items + 1) x (total_capacity + 1)
    # dp[i][w] sẽ lưu trữ giá trị tối đa khi xem xét i vật phẩm đầu tiên với sức chứa w
    dp_table = np.zeros((num_items + 1, total_capacity + 1), dtype=np.int32)

    # Điền bảng DP
    for i in range(1, num_items + 1):
        # Lấy giá trị và trọng lượng của vật phẩm thứ i (sử dụng chỉ số i-1 cho mảng gốc)
        current_value = item_values[i-1]
        current_weight = item_weights[i-1]

        for w in range(1, total_capacity + 1):
            # Nếu trọng lượng của vật phẩm hiện tại lớn hơn sức chứa hiện tại
            if current_weight > w:
                # Không thể chọn vật phẩm này, lấy giá trị từ trường hợp trước đó
                dp_table[i, w] = dp_table[i-1, w]
            else:
                # Chọn giá trị lớn hơn giữa:
                # 1. Không chọn vật phẩm hiện tại (dp_table[i-1, w])
                # 2. Chọn vật phẩm hiện tại (current_value + dp_table[i-1, w - current_weight])
                dp_table[i, w] = max(dp_table[i-1, w], current_value + dp_table[i-1, w - current_weight])

    # Kết quả cuối cùng nằm ở ô cuối cùng của bảng DP
    return dp_table[num_items, total_capacity]

if __name__ == '__main__':
    # Giá trị của các vật phẩm
    values = [100, 70, 50, 10]
    # Trọng lượng của các vật phẩm
    weights = [10, 4, 6, 12]
    # Sức chứa tối đa của ba lô
    max_capacity = 12
    # Số lượng vật phẩm
    n_items = len(values)

    result = solve_knapsack_dp(values, weights, max_capacity, n_items)
    print(f"Giá trị tối đa có thể đạt được: {result}")