0/1 Khắc phục sự cố về chiếc ba lô bằng ví dụ về lập trình động

Vấn đề về chiếc ba lô là gì?

Vấn đề về Knapsack Đây là một bài toán tối ưu tổ hợp kinh điển. Một siêu thị... n gói (n ≤ 100). Gói i Một kiện hàng có trọng lượng W[i] ≤ 100 và giá trị V[i] ≤ 100. Tên trộm không thể mang trọng lượng vượt quá sức chứa M (M ≤ 100). Tên trộm nên lấy những kiện hàng nào để tối đa hóa tổng giá trị?

Đầu vào:

• Trọng lượng tối đa M và số lượng kiện hàng n.
• Mảng có trọng số W[i] và giá trị tương ứng V[i].

Đầu ra:

• Tổng giá trị tối đa có thể đạt được trong phạm vi công suất cho phép.
• Bộ bưu kiện chính xác mà tên trộm nên lấy.

Thuật toán Knapsack được chia thành hai biến thể nổi tiếng:

• Bài toán ba lô 0/1 Bài toán được giải bằng Lập trình động. Mỗi kiện hàng hoặc được lấy toàn bộ hoặc bị bỏ lại — không có phần lẻ và không có kiện hàng trùng lặp.
• Bài toán ba lô phân số Bài toán được giải quyết bằng chiến lược tham lam. Ở đây, bạn có thể lấy một phần nhỏ của bất kỳ gói hàng nào để lấp đầy dung lượng còn lại.

Cách giải quyết vấn đề về chiếc ba lô bằng lập trình động với ví dụ

Phương pháp chia để trị chia một vấn đề lớn thành các vấn đề nhỏ hơn, rồi tiếp tục chia nhỏ cho đến khi mỗi vấn đề nhỏ đều dễ giải quyết. Tuy nhiên, phương pháp đệ quy thông thường thường giải quyết cùng một vấn đề nhỏ nhiều lần và lãng phí công sức.

Ý tưởng cốt lõi của Lập trình động bài toán cái túi (Knapsack Dynamic Programming) là lưu trữ mọi bài toán con đã được giải trong một bảng. Các lần gọi lặp lại sẽ đọc câu trả lời thay vì tính toán lại, biến thuật toán đệ quy có độ phức tạp theo cấp số mũ thành mã có độ phức tạp đa thức.

Giải quyết vấn đề về chiếc ba lô bằng lập trình động

Để thiết kế một giải pháp Lập trình động, bạn cần thực hiện bốn bước sau:

• Hãy giải quyết các bài toán con nhỏ nhất trước.
• Hãy suy ra một công thức truy hồi để xây dựng lời giải cho bài toán con từ các bài toán con nhỏ hơn.
• Lưu trữ các đáp án của bài toán con vào một bảng được tính toán từ dưới lên bằng cách sử dụng công thức truy hồi.
• Hãy ghép các thông tin từ bảng đã điền đầy đủ để đưa ra câu trả lời cuối cùng.

Phân tích bài toán chiếc ba lô 0/1

Giá trị tối ưu phụ thuộc vào hai yếu tố độc lập:

1. Hiện vẫn còn bao nhiêu gói thầu đang được xem xét?
2. Trọng lượng còn lại mà ba lô vẫn có thể chứa được.

Vì hàm mục tiêu phụ thuộc vào hai đại lượng, nên bảng các phương án phải là bảng hai chiều. Giả sử B[i][j] ký hiệu giá trị tối đa khi lựa chọn giữa các gói {1, …, i} với giới hạn trọng lượng j.

• Câu trả lời cuối cùng là B[n][M], tổng giá trị tốt nhất trên tất cả n gói hàng với dung lượng M.
• Tổng trọng lượng được chọn luôn bị giới hạn bởi dung lượng hiện tại: B[i][j] ≤ j.

Ví dụ: nếu B[4][10] = 8, tổng trọng lượng tốt nhất từ ​​bốn gói đầu tiên dưới mức dung lượng 10 là 8. Một số trong bốn gói đó có thể bị bỏ qua.

Công thức tính B[i][j]

• W[i], V[i] là trọng lượng và giá trị của kiện hàng i, trong đó i thuộc tập hợp {1, …, n}.
• M là trọng lượng tối đa mà ba lô có thể mang được.

Trường hợp cơ bản với một gói: đối với mọi dung lượng j ≥ W[1]:

B[1][j] = W[1]

Trong trường hợp tổng quát, hãy quyết định xem có nên bao gồm gói hàng i vào dung lượng j hay không:

• Nếu gói i là bỏ qua, B[i][j] bằng giá trị tốt nhất khi sử dụng các gói {1, …, i-1} với dung lượng j:

B[i][j] = B[i - 1][j]

• Nếu gói i là Lấy (chỉ được phép khi W[i] ≤ j), B[i][j] bằng V[i] cộng với giá trị tốt nhất từ ​​các gói {1, …, i-1} trong phạm vi dung lượng j – W[i]:

B[i][j] = V[i] + B[i - 1][j - W[i]]

Chọn ứng viên có kích thước lớn hơn trong hai ứng viên.

Cơ sở của lập trình động

Kết hợp hai trường hợp này sẽ cho ra phương trình tái phát đầy đủ:

B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])

Trường hợp cơ bản là B[0][j] = 0 với mọi j, vì không có gói nào thì giá trị bằng không bất kể dung lượng.

Tính Bảng Tùy Chọn

Xây dựng bảng B bằng cách sử dụng công thức truy hồi. Sau khi bảng B được điền đầy đủ, bảng đó sẽ được sử dụng để xây dựng bảng tiếp theo. trace-back tái cấu trúc các gói đã chọn. Bảng B có n + 1 hàng và M + 1 cột:

• Hàng 0 là trường hợp cơ bản, được điền toàn số 0.
• Sử dụng hàng 0 để tính hàng 1, hàng 1 để tính hàng 2, và tiếp tục cho đến khi hoàn thành hàng n.

Bảng tùy chọn

Trace

Sau khi hoàn thành bước B, hãy tập trung vào... B[n][M], tổng giá trị tối ưu trên tất cả n gói hàng có dung lượng M.

• If B[n][M] = B[n-1][M]Gói n không được chọn, vì vậy hãy tiếp tục. tractừ B[n-1][M].
• If B[n][M] ≠ B[n-1][M]Gói n đã được chọn, vì vậy hãy tiếp tục. tractừ B[n-1][M – W[n]].

Lặp lại cho đến khi bạn đến hàng số 0 của bảng.

Thuật toán tra cứu bảng tùy chọn để tìm các gói hàng đã chọn

Lưu ý: bất cứ khi nào B[i][j] = B[i-1][j]Gói i chưa được chọn. Giá trị B[n][M] là tổng giá trị tối ưu được đóng gói trong ba lô.

Các bước cho tracbao gồm các gói đã chọn:

• Bước 1: Bắt đầu từ i = n, j = M.
• Bước 2: Quét cột j từ dưới lên cho đến khi bạn tìm thấy hàng i sao cho B[i][j] > B[i-1][j]. Đánh dấu gói i là đã được chọn: Select[i] = true.
• Bước 3: Cập nhật j = j – W[i]. Nếu j > 0, quay lại Bước 2, nếu không thì chuyển đến Bước 4.
• Bước 4: In tất cả các gói hàng đã được chọn.

Java Code

Sau đây Java Phương thức này điền dữ liệu vào B[][] từ dưới lên, in bảng ra để kiểm tra, và sau đó traclà các gói đã chọn.

public void knapsackDyProg(int W[], int V[], int M, int n) {
    int B[][] = new int[n + 1][M + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= M; j++) {
            B[i][j] = 0;
        }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            B[i][j] = B[i - 1][j];

            if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
                B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1];
            }

            System.out.print(B[i][j] + " ");
        }
        System.out.print("\n");
    }

    System.out.println("Max Value:\t" + B[n][M]);
    System.out.println("Selected Packs: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Hàm ba lôDyProg() trong Java

Giải thích mã:

1. Bảng phân bổ B[][] và khởi tạo mỗi ô về 0.
2. Điền vào B[][] từ dưới lên bằng cách sử dụng công thức truy hồi từ phần trước.
3. Bắt đầu mỗi ô với giá trị “bỏ qua gói i” B[i-1][j].
4. Nếu việc chọn gói i khả thi và mang lại giá trị tốt hơn hẳn, hãy ghi đè lên ô đó.
5. TracDi chuyển các mục đã chọn từ hàng n trở lại hàng 0.
6. Mỗi khi gói hàng n được chọn, hãy giảm dung lượng còn lại đi. W[n-1].

Ghi chú sửa lỗi: đoạn mã gốc đã thay đổi tham số M trong khi vẫn đang đọc B[n][M]Phiên bản an toàn hơn ở trên sử dụng một con trỏ riêng biệt. j cho trace.

Java Người điều khiển chạy thuật toán trên hai ví dụ đã được xử lý:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Kết quả đầu ra cho ví dụ đầu tiên:

0 0 0 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7
0 0 0 3 4 4 4 7 7 8 8 8
0 0 0 3 4 4 4 7 7 10 10 10
0 0 0 3 4 4 4 7 8 10 10 11
Max Value:	11
Selected Packs:
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3

Kết quả cho ví dụ thứ hai:

0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs:
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Độ phức tạp về thời gian và không gian của bài toán ba lô 0/1

• Độ phức tạp về thời gian: O(n · M) — hai vòng lặp lồng nhau quét n mục qua M+1 trạng thái dung lượng.
• Độ phức tạp không gian: O(n · M) cho toàn bộ bảng, có thể giảm xuống O(M) bằng cách giữ nguyênping chỉ hàng trước đó khi tracKhông cần xác nhận lại bằng email.

Thời gian chạy là đa thức giả: đa thức theo giá trị của M nhưng hàm mũ theo số bit được sử dụng để mã hóa M. Đó là lý do tại sao bài toán ba lô 0/1 vẫn là NP-khó mặc dù lập trình động hiệu quả trong thực tế.

Ứng dụng của bài toán ba lô 0/1

• Xếp dỡ hàng hóa, đóng gói container và lấy hàng trong kho theo giới hạn trọng lượng.
• Phân bổ ngân sách cho các dự án đầu tư có chi phí cố định và lợi nhuận dự kiến.
• Các vấn đề về cắt vật liệu trong sản xuất khi không thể chia nhỏ từng mảnh.
• Các thuật toán mật mã như Merkle-Hellman được xây dựng dựa trên độ khó của bài toán cái túi.
• Lập lịch trình với các ràng buộc về tài nguyên trong điện toán đám mây và phân bổ tác vụ CPU.
• Lựa chọn đặc trưng trong học máy với ngân sách đặc trưng cố định.

Câu Hỏi Thường Gặp