0/1 Knapsack Problem

Q: Làm thế nào để tìm ra những món đồ mà bài toán ba lô 0/1 đã chọn?

Giữ lại toàn bộ bảng rồi lần ngược từ best[n][capacity] . Nếu best[i][c] khác best[i-1][c] , thì món đồ i-1 đã được đóng gói, vì vậy hãy ghi lại món đồ đó và trừ trọng lượng của nó khỏi c . Nếu không, hãy chuyển lên hàng i-1 với cùng giá trị c .

Trung bìnhQuy hoạch động

+10

Bạn có n món đồ. Món đồ i nặng weights[i] và có giá trị values[i]. Túi của bạn chứa được tổng trọng lượng tối đa là capacity. Mỗi món đồ chỉ có một món, và bạn có thể chọn mang theo nguyên món hoặc để lại. Hãy trả về tổng giá trị lớn nhất mà bạn có thể mang theo.

Hàm

knapsack(weights: integer-array, values: integer-array, capacity: integer) → integer

weightsinteger-array: trọng số của từng mục
valuesinteger-array: giá trị của mỗi phần tử
capacityinteger: trọng lượng lớn nhất mà chiếc túi có thể mang
Trả vềinteger: tổng giá trị lớn nhất của các món đồ có tổng trọng lượng nằm trong giới hạn sức chứa

Ràng buộc

1 ≤ n ≤ 100, trong đó n = weights.length = values.length
1 ≤ weights[i] ≤ 1000
1 ≤ values[i] ≤ 10⁴
1 ≤ capacity ≤ 1000

Ví dụ

Đầu vào: weights = [4, 2, 3, 5]values = [10, 4, 7, 12]capacity = 7
Đầu ra: 17
Giải thích: Món đồ 0 và 2 có tổng trọng lượng 4 + 3 = 7 và tổng giá trị 10 + 7 = 17. Nếu xếp món đồ có giá trị cao nhất trước (trọng lượng 5, giá trị 12), bạn chỉ còn chỗ cho món đồ 1, tổng giá trị là 16.

Câu hỏi mở rộng

Giả sử sức chứa có thể đạt đến 10^9, trong khi tổng các giá trị nhiều nhất là 10^4. Bạn sẽ dùng gì làm chỉ số cho bảng?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Không có thứ tự tham lam (greedy) nào hiệu quả: chọn món đồ có giá trị cao nhất trước chỉ đạt 16, không phải 17, trong ví dụ đầu tiên. Giá trị tốt nhất tính từ món đồ i trở đi chỉ phụ thuộc vào i và sức chứa còn lại, là một số nguyên không quá 1000. Mỗi cặp cần một ô trong bảng, cho độ phức tạp O(n × capacity), và chỉ cần một hàng nếu bạn duyệt sức chứa theo thứ tự giảm dần.

Hãy thử cả hai lựa chọn cho mỗi mục

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Gọi best(i, room) là giá trị lớn nhất mà các món đồ từ i trở đi có thể thêm vào khi còn trống room đơn vị; nếu đã qua món đồ cuối cùng thì giá trị là 0. Bỏ qua món đồ i sẽ cho best(i+1, room). Nếu đóng gói món đồ đó khi weights[i] ≤ room, ta có values[i] + best(i+1, room-weights[i]). Hãy giữ lại giá trị lớn hơn. Mỗi cách đóng gói phù hợp là một chuỗi lựa chọn đóng gói hoặc bỏ qua, và đệ quy sẽ thử tất cả các cách đó.

Mỗi món đồ làm số đường đi tăng gấp đôi. Khi cả 100 món đồ đều vừa, chẳng hạn mỗi món nặng 10 và chiếc túi có sức chứa 1000, sẽ có 2^100 đường đi.

Thuật toán

Viết best(i, room); trả về 0 khi i vượt quá món đồ cuối cùng.
Đặt skip bằng best(i+1, room).
Nếu weights[i] > room, trả về skip.
Nếu không, trả về giá trị lớn hơn giữa skip và values[i] + best(i+1, room-weights[i]).
Trả về best(0, capacity).

def knapsack(weights, values, capacity):
    n = len(weights)

    # The most value items i, i+1, ... can add with room units of weight left
    def best(i, room):
        if i == n:
            return 0
        skip = best(i + 1, room)
        if weights[i] > room:
            return skip
        take = values[i] + best(i + 1, room - weights[i])
        return max(skip, take)

    return best(0, capacity)

Điền bảng theo mặt hàng và sức chứa

Ý tưởng

Đệ quy đi đến cùng một cặp (i, room) theo nhiều đường đi. Có nhiều nhất 101 × 1001, khoảng 10^5 cặp, vì vậy hãy tính mỗi cặp một lần.

Gọi best[i][c] là giá trị lớn nhất mà i món đồ đầu tiên có thể cho vào túi sức chứa c; hàng 0 gồm toàn số 0. Với món đồ i-1 có trọng lượng w và giá trị v, bỏ món đồ đó thì được best[i-1][c], còn cho món đồ đó vào túi, khi w ≤ c, thì được best[i-1][c-w] + v. Hàng i chỉ đọc hàng i-1, vì vậy mỗi món đồ chỉ được tính vào một ô tối đa một lần.

Trong ví dụ đầu tiên, món đồ 2 (trọng lượng 3, giá trị 7) nâng sức chứa 7 lên thành best[2][4] + 7 = 17. Sau đó, món đồ 3 chỉ đưa ra best[3][2] + 12 = 16, nên đáp án vẫn là 17.

Thuật toán

Tạo bảng gồm n+1 hàng và capacity+1 cột, tất cả đều bằng 0.
Với mỗi hàng i từ 1 đến n, lấy w = weights[i-1] và v = values[i-1].
Với mỗi sức chứa c, đặt best[i][c] bằng best[i-1][c].
Nếu w ≤ c và best[i-1][c-w] + v lớn hơn, hãy lưu giá trị đó thay thế.
Trả về best[n][capacity].

def knapsack(weights, values, capacity):
    n = len(weights)
    # best[i][c]: the most value from the first i items within capacity c
    best = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(capacity + 1):
            best[i][c] = best[i - 1][c]  # leave item i-1 out
            if w <= c and best[i - 1][c - w] + v > best[i][c]:
                best[i][c] = best[i - 1][c - w] + v  # put it in
    return best[n][capacity]

Một hàng, các sức chứa giảm dần

Ý tưởng

Hàng i chỉ cần hàng i-1, vì vậy hãy giữ một hàng best[c] và ghi đè từng mục. Hướng duyệt quyết định đáp án có đúng hay không.

Khi duyệt c tăng dần, best[c-w] có thể đã bao gồm mục hiện tại. Với một mục có trọng lượng 3 và giá trị 5, sức chứa 6 khiến sức chứa 3 có giá trị 5, sau đó sức chứa 6 đọc giá trị này và trở thành 10: hai bản sao. Khi duyệt giảm dần từ capacity đến w, ô bạn đọc nằm phía dưới ô bạn ghi và sẽ bị ghi đè sau đó, nên nó vẫn giữ giá trị của hàng trước.

Duyệt tăng dần là vòng lặp phù hợp khi có thể lấy các mục không giới hạn số bản sao. Ở đây, thời gian vẫn là O(n × capacity) và bộ nhớ giảm còn một hàng.

Thuật toán

Tạo best với capacity + 1 phần tử, tất cả đều bằng 0.
Với mỗi món đồ có trọng lượng w và giá trị v, duyệt c từ capacity giảm dần đến w.
Nếu best[c-w] + v lớn hơn best[c], lưu giá trị đó vào best[c].
Trả về best[capacity].

def knapsack(weights, values, capacity):
    # best[c]: the most value from the items seen so far within capacity c
    best = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Walk the capacities downward so each item goes in at most once
        for c in range(capacity, w - 1, -1):
            if best[c - w] + v > best[c]:
                best[c] = best[c - w] + v
    return best[capacity]

Lỗi thường gặp và trường hợp biên

Duyệt sức chứa theo chiều tăng dần trong phiên bản một hàng sẽ khiến một món đồ được tính hai lần: một món đồ có trọng lượng 3 và giá trị 5 trong chiếc túi có sức chứa 6 đạt điểm 10 thay vì 5.
Dùng một hàng gồm capacity phần tử thay vì capacity + 1. Khi trả về best[capacity-1], ta sẽ bỏ sót cách đóng gói lấp đầy chính xác chiếc túi, chẳng hạn như món đồ có trọng lượng 1 trong chiếc túi có sức chứa 1.
Khởi tạo các phần tử bằng âm vô cực. Chiếc túi không cần phải đầy, vì vậy mọi phần tử đều bắt đầu bằng 0; nếu dùng âm vô cực, ví dụ thứ ba sẽ trả về âm vô cực thay vì 0.
Phải bỏ qua món đồ nặng hơn sức chứa của túi. Trong ví dụ thứ ba, phạm vi đóng w...capacity khiến chương trình dừng trong Swift, còn (w+1):(capacity+1) đếm ngược trong R.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán ba lô 0/1 là bao nhiêu?

Bảng này chạy trong thời gian O(n × capacity), khoảng 10^5 bước với 100 vật phẩm và sức chứa 1000, còn phiên bản một hàng dùng bộ nhớ O(capacity). Giới hạn này là giả đa thức: nó tăng theo giá trị của sức chứa, không phải theo số chữ số của sức chứa. Bài toán tổng quát là NP-khó.

Tại sao thuật toán tham lam không giải được bài toán ba lô 0/1?

Quy tắc tham lam (greedy rule) không bao giờ hoàn tác một lựa chọn, ngay cả khi món đồ được chọn để lại khoảng trống mà không món nào lấp đầy. Với sức chứa 7, món đồ có trọng lượng 5 và giá trị 10 có tỷ lệ tốt nhất ngang bằng với các món khác, nhưng hai món đồ có trọng lượng 4 và 3 cộng lại có giá trị 13. Cách tham lam theo tỷ lệ chỉ tối ưu cho bài toán ba lô phân số (fractional knapsack), trong đó bạn có thể cắt nhỏ các món đồ.

Làm thế nào để tìm ra những món đồ mà bài toán ba lô 0/1 đã chọn?

Giữ lại toàn bộ bảng rồi lần ngược từ best[n][capacity]. Nếu best[i][c] khác best[i-1][c], thì món đồ i-1 đã được đóng gói, vì vậy hãy ghi lại món đồ đó và trừ trọng lượng của nó khỏi c. Nếu không, hãy chuyển lên hàng i-1 với cùng giá trị c.

def knapsack(weights, values, capacity):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

weights = [4, 2, 3, 5]
values = [10, 4, 7, 12]
capacity = 7

Đầu ra mong đợi

0/1 Knapsack Problem

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Hãy thử cả hai lựa chọn cho mỗi mục

Điền bảng theo mặt hàng và sức chứa

Một hàng, các sức chứa giảm dần

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự