0/1 Khắc phục sự cố về chiếc ba lô bằng ví dụ về lập trình động
Sarah Chen
Vấn đề về chiếc ba lô là gì?
Vấn đề về Knapsack thuật toán là một bài toán rất hữu ích trong tổ hợp. Trong siêu thị có n gói hàng (n ≤ 100) gói hàng i có trọng lượng W[i] ≤ 100 và giá trị V[i] ≤ 100. Kẻ trộm đột nhập vào siêu thị, tên trộm không được mang trọng lượng vượt quá M (M ≤ 100) ). Vấn đề cần giải quyết ở đây là: tên trộm sẽ lấy đi gói hàng nào để có giá trị cao nhất?
Đầ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ối đa hóa giá trị và trọng lượng tương ứng trong công suất.
- Những gói hàng nào tên trộm sẽ lấy đi.
Thuật toán Knapsack có thể được chia thành hai loại:
- Bài toán Ba lô 0/1 sử dụng quy hoạch động. Trong loại thuật toán Knapsack này, mỗi gói hàng có thể được lấy hoặc không. Ngoài ra, kẻ trộm không thể lấy một phần nhỏ của gói hàng đã lấy hoặc lấy gói hàng nhiều lần. Loại này có thể được giải quyết bằng Phương pháp lập trình động.
- Thuật toán bài toán Ba lô phân số. Loại này có thể được giải quyết bằng Chiến lược tham lam.
Cách giải quyết vấn đề về chiếc ba lô bằng lập trình động với ví dụ
Trong chiến lược chia để trị, bạn chia vấn đề cần giải quyết thành các bài toán con. Các bài toán con lại được chia thành các bài toán con nhỏ hơn. Nhiệm vụ đó sẽ tiếp tục cho đến khi bạn gặp được các bài toán con có thể giải được dễ dàng. Tuy nhiên, trong quá trình phân chia như vậy, bạn có thể gặp phải vấn đề tương tự nhiều lần.
Ý tưởng cơ bản của lập trình động Knapsack là sử dụng bảng để lưu trữ lời giải của các bài toán con đã được giải. Nếu gặp lại bài toán con, bạn chỉ cần lấy lời giải trong bảng mà không cần phải giải lại. Vì vậy, các thuật toán được thiết kế bằng quy hoạch động rất hiệu quả.
Để giải quyết một vấn đề bằng lập trình động, bạn cần thực hiện các nhiệm vụ sau:
- Tìm lời giải của các bài toán con nhỏ nhất.
- Tìm ra công thức (hoặc quy tắc) để xây dựng lời giải của bài toán con thông qua lời giải của bài toán con dù nhỏ nhất.
- Tạo một bảng lưu trữ lời giải của các bài toán con. Sau đó tính nghiệm của bài toán con theo công thức tìm được và lưu vào bảng.
- Từ các bài toán con đã giải, bạn tìm ra lời giải của bài toán ban đầu.
Phân tích bài toán chiếc ba lô 0/1
Khi phân tích bài toán Knapsack 0/1 bằng lập trình Dynamic, bạn có thể nhận thấy một số điểm đáng chú ý. Giá trị của thuật toán ba lô phụ thuộc vào hai yếu tố:
- Có bao nhiêu gói đang được xem xét
- Trọng lượng còn lại mà ba lô có thể chứa được.
Vì vậy, bạn có hai đại lượng thay đổi.
Với lập trình động, bạn có thông tin hữu ích:
- hàm mục tiêu sẽ phụ thuộc vào hai đại lượng thay đổi
- bảng tùy chọn sẽ là bảng 2 chiều.
Nếu gọi B[i][j] là giá trị lớn nhất có thể bằng cách chọn trong các gói {1, 2, …, i} có giới hạn trọng lượng j.
- Giá trị lớn nhất khi được chọn trong n kiện hàng có giới hạn trọng lượng M là B[n][M]. Nói cách khác: Khi có i kiện hàng cần chọn, B[i][j] là trọng lượng tối ưu khi trọng lượng tối đa của ba lô là j.
- Trọng số tối ưu luôn nhỏ hơn hoặc bằng trọng số tối đa: B[i][j] ≤ j.
Ví dụ: B[4][10] = 8. Nghĩa là trong trường hợp tối ưu, tổng trọng lượng của các kiện hàng được chọn là 8, khi có 4 kiện hàng đầu tiên được chọn (gói thứ 1 đến gói thứ 4) và trọng lượng tối đa của ba lô là 10. Không nhất thiết phải chọn cả 4 món.
Công thức tính B[i][j]
Đầu vào, bạn xác định:
- W[i], V[i] lần lượt là trọng lượng và giá trị của kiện hàng i, trong đó i
![Công thức tính B[i][j]](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%2016%2023'%3E%3C/svg%3E)
{1, …, n}. - M là trọng lượng tối đa mà ba lô có thể mang được.
![Công thức tính B[i][j]](https://www.guru99.com/images/1/043019_0611_KnapsackPro4.png){kind=small}
{1, …, n}.Trong trường hợp đơn giản chỉ có 1 gói để lựa chọn. Bạn tính B[1][j] cho mỗi j: tức là trọng lượng tối đa của ba lô ≥ trọng lượng của kiện hàng thứ nhất
B[1][j] = W[1]
Với giới hạn trọng lượng j, việc lựa chọn tối ưu giữa các gói {1, 2, …, i – 1, i} để có giá trị lớn nhất sẽ có hai khả năng:
- Nếu gói i không được chọn thì B[i][j] là giá trị lớn nhất có thể bằng cách chọn trong số các gói {1, 2, …, i – 1} với giới hạn trọng lượng là j. Bạn có:
B[i][j] = B[i – 1][j]
- Nếu chọn gói i (tất nhiên chỉ xét trường hợp này khi W[i] ≤ j) thì B[i][j] bằng giá trị V[i] của gói i cộng với giá trị lớn nhất có thể đạt được bằng cách chọn trong số gói hàng {1, 2, …, i – 1} có giới hạn trọng lượng (j – W[i]). Nghĩa là, xét về giá trị bạn có:
B[i][j] = V[i] + B[i – 1][j – W[i]]
Do tạo ra B[i][j] là giá trị lớn nhất có thể nên B[i][j] sẽ là giá trị lớn nhất của 2 giá trị trên.
Cơ sở của lập trình động
Vì vậy, bạn phải cân nhắc xem có nên chọn gói i hay không. Từ đó bạn có công thức đệ quy như sau:
B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]
Dễ dàng thấy B[0][j] = giá trị tối đa có thể bằng cách chọn từ 0 gói = 0.
Tính Bảng Tùy Chọn
Bạn xây dựng bảng tùy chọn dựa trên công thức đệ quy trên. Để kiểm tra kết quả có đúng không (nếu không chính xác bạn xây dựng lại hàm mục tiêu B[i][j]). Thông qua việc tạo hàm mục tiêu B[i][j] và bảng tùy chọn, bạn sẽ định hướng việc dò tìm.
Bảng phương án B gồm n+1 dòng, M+1 cột,
- Thứ nhất, chứa đầy cơ sở của quy hoạch động: Dòng 0 bao gồm tất cả các số XNUMX.
- Dùng công thức đệ quy, dùng dòng 0 để tính dòng 1, dùng dòng 1 để tính dòng 2, v.v… cho đến khi tính hết các dòng.
Dấu vết
Khi tính toán bảng phương án, bạn quan tâm đến B[n][M] là giá trị lớn nhất thu được khi chọn trong tất cả n gói hàng có giới hạn trọng lượng M.
- If B[n][M] = B[n – 1][M] thì gói n không được chọn, bạn theo dõi B[n – 1][M].
- If B[n][M] ≠ B[n – 1][M], bạn nhận thấy rằng lựa chọn tối ưu có gói n và vết B[n – 1][M – W[n]].
Tiếp tục theo dõi cho đến khi đến hàng 0 của bảng tùy chọn.
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 ý: Nếu B[i][j] = B[i – 1][j] thì gói i không được chọn. B[n][W] là tổng giá trị tối ưu của gói hàng được cho vào ba lô.
Các bước truy vết:
- Bước 1: Bắt đầu từ i = n, j = M.
- Bước 2: Nhìn vào cột j từ dưới lên tìm dòng i sao cho B[i][j] > B[i – 1][j]. Đánh dấu gói đã chọn i: Chọn [i] = true;
- Bước 3: j = B[i][j] – W[i]. Nếu j > 0, chuyển sang bước 2, nếu không chuyển sang bước 4
- Bước 4: Dựa vào bảng tùy chọn để in các gói đã chọn.
Java Mã
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: ");
while (n != 0) {
if (B[n][M] != B[n - 1][M]) {
System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
M = M - W[n-1];
}
n--;
}
}
Giải thích về mã Knapsack:
- Tạo bảng B[][]. Đặt giá trị mặc định cho mỗi ô là 0.
- Xây dựng bảng B[][] theo cách từ dưới lên. Tính toán bảng phương án bằng công thức truy xuất.
- Tính B[i][j]. Nếu bạn không chọn gói i.
- Sau đó đánh giá: nếu chọn gói i thì có lợi hơn thì reset B[i][j].
- Theo dõi bảng từ hàng n đến hàng 0.
- Nếu bạn chọn gói n. Sau khi chọn gói n, chỉ có thể thêm trọng số M – W[n – 1].
Trong hướng dẫn này, bạn có hai ví dụ. Đây là mã java để chạy chương trình trên với hai ví dụ:
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{3, 4, 5, 9, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{3, 4, 4, 10, 4};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 11;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackDyProg(W, V, M, n);
}
Bạn có đầu ra:
- 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
- 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
