Rod Cutting Problem

Q: Độ phức tạp thời gian của bài toán cắt thanh là gì?

Bảng cần thời gian O(n²) và bộ nhớ O(n): độ dài len thử len đoạn đầu tiên, tổng cộng có n(n+1)/2 lần thử. Nếu không lưu các đáp án, đệ quy sẽ gọi chính xác 2^n lần với thanh có độ dài n, vì mỗi độ dài đều gọi mọi độ dài ngắn hơn.

Q: Vì sao bài toán cắt thanh là một bài toán ba lô không giới hạn?

Xem mỗi đoạn có độ dài k là một món đồ có trọng lượng k và giá trị prices[k-1] , với số lượng không giới hạn, còn thanh gỗ là một chiếc túi có sức chứa n cần được lấp đầy chính xác. Khi đó, tổng giá trị lớn nhất của các món đồ chính là giá bán tốt nhất của thanh gỗ.

Q: Làm thế nào để tìm vị trí cắt thanh que?

Với mỗi độ dài, hãy lưu lại đoạn cắt đầu tiên k giúp đạt mức giá tốt nhất. Bắt đầu từ độ dài n: cắt một đoạn có độ dài đã lưu, chuyển sang độ dài còn lại rồi lặp lại cho đến khi độ dài đó bằng 0. Các đoạn cắt tạo thành một phương án tối ưu.

Trung bìnhQuy hoạch động

+10

Bạn có một thanh có độ dài n, trong đó n = prices.length. Một đoạn có độ dài k bán được với giá prices[k-1]. Bạn có thể cắt thanh thành bao nhiêu đoạn tùy thích, mỗi đoạn có độ dài nguyên, hoặc bán nguyên thanh. Hãy trả về số tiền nhiều nhất bạn có thể kiếm được bằng cách bán toàn bộ thanh.

Hàm

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] là giá của một đoạn có độ dài k; thanh dài prices.length
Trả vềinteger: số tiền tối đa mà cả cây cần câu có thể kiếm được

Ràng buộc

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

Ví dụ

Đầu vào: prices = [2, 5, 7, 8]
Đầu ra: 10
Giải thích: Bán hai đoạn dài 2 thu được 5 + 5 = 10. Bán nguyên thanh kiếm được 8, còn bán một đoạn dài 1 và một đoạn dài 3 thu được 2 + 7 = 9.

Câu hỏi mở rộng

Nếu bạn có thể cắt thanh gỗ nhiều nhất m lần thì sao? Khi đó, mỗi mục trong bảng cần biết điều gì?

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

Một thanh dài n có 2^(n-1) cách cắt. Bạn không cần liệt kê tất cả: dù mảnh đầu tiên dài bao nhiêu, phần còn lại vẫn là một thanh ngắn hơn và đặt ra cùng câu hỏi. Vì vậy, chỉ có n+1 đáp án, mỗi độ dài có một đáp án, và tính các đáp án từ độ dài ngắn nhất trở lên cần O(n²) bước.

Hãy thử mọi độ dài cho mảnh đầu tiên

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

Ý tưởng

Dù chọn phương án nào, đoạn ở đầu bên trái có độ dài k từ 1 đến độ dài của thanh và mang lại prices[k-1]; phần còn lại của phương án cắt một thanh có độ dài length-k. Vì vậy, best(length) bằng 0 khi độ dài là 0, còn nếu không thì bằng giá trị lớn nhất trong số prices[k-1] + best(length-k) với mọi k, trong đó k = length nghĩa là bán nguyên thanh. Mọi phương án đều có một đoạn đầu tiên, nên giá trị lớn nhất này bao quát mọi phương án.

Mỗi lần gọi phân nhánh thành mọi độ dài ngắn hơn, nên số lần gọi tăng gấp đôi theo mỗi đơn vị độ dài: với một thanh dài 40, số lần gọi vào khoảng 2^40, tức 10^12.

Thuật toán

Viết best(length), hàm này trả về 0 khi length bằng 0.
Với mỗi đoạn đầu tiên k từ 1 đến length, tính prices[k-1] + best(length-k).
Trả về giá trị lớn nhất trong các giá trị đó.
Trả về best(n).

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

Giá tốt nhất cho mỗi độ dài, ngắn nhất trước

Ý tưởng

Đệ quy tính toán lại các giá trị giống nhau: best(2) được best(3), best(4) và mọi thanh dài hơn yêu cầu tính. Chỉ có n+1 độ dài, vì vậy hãy tính mỗi độ dài một lần và lưu vào mảng best. Mỗi độ dài chỉ đọc các độ dài ngắn hơn, nên điền mảng từ 0 trở lên sẽ đảm bảo mọi giá trị đã sẵn sàng khi được đọc.

Với [2, 5, 7, 8]: best[1] là 2, best[2] là số lớn hơn trong 2 + 2 và 5, tức là 5, best[3] là 7, còn best[4] là số lớn nhất trong 2 + 7, 5 + 5, 7 + 2 và 8, tức là 10.

Không giống bài toán cái túi 0/1, best[len-k] có thể đã chứa các đoạn dài k, và đó chính là điều bạn muốn, vì bạn có thể cắt một độ dài thành bao nhiêu đoạn tùy thích. Độ dài len thử các đoạn đầu tiên có độ dài từ 1 đến len: tổng cộng n(n+1)/2 bước, khoảng 5 × 10^5 với một thanh dài 1000.

Thuật toán

Tạo best có n + 1 phần tử, tất cả đều bằng 0.
Với mỗi length từ 1 đến n, thử mọi đoạn đầu tiên k từ 1 đến length.
Tính prices[k-1] + best[length-k] và giữ giá trị lớn nhất trong best[length].
Trả về best[n].

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

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

Đọc prices[k] cho chiều dài k. Cách đó định giá mỗi đoạn dài hơn một đơn vị và vượt quá cuối mảng tại k = n; hãy dùng prices[k-1].
Bỏ qua k = length, tức đoạn không cắt. Khi đó best[1] vẫn là 0, và [1, 3, 8] đạt điểm 3 thay vì 8.
Cắt tham lam theo giá tốt nhất trên mỗi đơn vị. Với [2, 7, 11, 13], chiều dài 3 có giá trên mỗi đơn vị cao nhất, nhưng 11 cho đoạn đó cộng với 2 cho phần còn lại chỉ được 13, trong khi hai đoạn dài 2 được 14.
Ghi nhớ kết quả theo hướng từ trên xuống trong Python. Đệ quy vẫn lồng sâu theo chiều dài của thanh gỗ: thanh dài 1000 tạo ra 1001 lời gọi lồng nhau, vượt quá giới hạn mặc định là 1000. Hãy điền mảng theo hướng từ dưới lên.

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

Độ phức tạp thời gian của bài toán cắt thanh là gì?

Bảng cần thời gian O(n²) và bộ nhớ O(n): độ dài len thử len đoạn đầu tiên, tổng cộng có n(n+1)/2 lần thử. Nếu không lưu các đáp án, đệ quy sẽ gọi chính xác 2^n lần với thanh có độ dài n, vì mỗi độ dài đều gọi mọi độ dài ngắn hơn.

Vì sao bài toán cắt thanh là một bài toán ba lô không giới hạn?

Xem mỗi đoạn có độ dài k là một món đồ có trọng lượng k và giá trị prices[k-1], với số lượng không giới hạn, còn thanh gỗ là một chiếc túi có sức chứa n cần được lấp đầy chính xác. Khi đó, tổng giá trị lớn nhất của các món đồ chính là giá bán tốt nhất của thanh gỗ.

Làm thế nào để tìm vị trí cắt thanh que?

Với mỗi độ dài, hãy lưu lại đoạn cắt đầu tiên k giúp đạt mức giá tốt nhất. Bắt đầu từ độ dài n: cắt một đoạn có độ dài đã lưu, chuyển sang độ dài còn lại rồi lặp lại cho đến khi độ dài đó bằng 0. Các đoạn cắt tạo thành một phương án tối ưu.

Lời giải sẽ thay đổi thế nào nếu mỗi lần cắt đều tốn tiền?

Bán nguyên thanh không cần cắt, còn mọi đoạn đầu tiên khác đều cần một lần cắt. Vì vậy, best[len] là giá trị lớn hơn giữa prices[len-1] và giá trị lớn nhất trong các biểu thức prices[k-1] + best[len-k] - cost với k nhỏ hơn len. Phần còn lại của bảng giữ nguyên.

def cutRod(prices):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

prices = [2, 5, 7, 8]

Đầu ra mong đợi