Vấn đề Knapsack là gì?

Thuật toán vấn đề Knapsack là một vấn đề rất hữu ích trong tổ hợp. Trong siêu thị có n gói (n ≤ 100) gói i có trọng lượng W [i] ≤ 100 và giá trị V [i] ≤ 100. Một tên trộm đột nhập vào siêu thị, tên trộm không thể 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 gói nào để có được giá trị cao nhất?

Nhập:

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

Ra:

  • Tối đa hóa giá trị và trọng lượng tương ứng về công suất.
  • Gói nào tên trộm sẽ lấy đi.

Thuật toán Knapsack có thể được chia thành hai loại:

  • Sự cố Knapsack 0/1 sử dụng lập trình động. Trong loại thuật toán Knapsack này, mỗi gói có thể được thực hiện hoặc không được thực hiện. Bên cạnh đó, kẻ trộm không thể lấy một số tiền lẻ của một gói hàng được lấy hoặc lấy một 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 vấn đề Knapsack phân đoạn. Loại này có thể được giải quyết bằng Chiến lược Tham lam.

Trong hướng dẫn này, bạn sẽ tìm hiểu:

Giới thiệu tóm tắt về lập trình động

Trong chiến lược phân chia và chinh phục, bạn chia vấn đề cần giải quyết thành các subproblems. Các subproblems được chia thành các subproblems nhỏ hơn. Nhiệm vụ đó sẽ tiếp tục cho đến khi bạn nhận được các tiểu từ có thể được giải quyết dễ dàng. Tuy nhiên, trong quá trình phân chia như vậy, bạn có thể gặp phải cùng một vấn đề nhiều lần.

Ý tưởng cơ bản của lập trình động Knapsack là sử dụng một bảng để lưu trữ các giải pháp của các subproblems đã giải quyết. Nếu bạn phải đối mặt với một subproblem một lần nữa, bạn chỉ cần lấy các giải pháp trong bảng mà không cần phải giải quyết nó một lần nữa. Do đó, các thuật toán được thiết kế bởi lập trình động rất hiệu quả.

tóm tắt về lập trình động

Để giải quyết vấn đề bằng lập trình động, bạn cần thực hiện các tác vụ sau:

  • Tìm giải pháp của các subproblems nhỏ nhất.
  • Tìm hiểu công thức (hoặc quy tắc) để xây dựng một giải pháp tiểu từ thông qua các giải pháp của các tiểu từ nhỏ nhất.
  • Tạo bảng lưu trữ các giải pháp của subproblems. Sau đó tính toán dung dịch subproblem theo công thức tìm thấy và lưu vào bảng.
  • Từ các subproblems đã giải quyết, bạn tìm thấy giải pháp của vấn đề ban đầu.

Phân tích vấn đề Knapsack 0/1

Khi phân tích 0/1 bài toán Knapsack bằng lập trình động, bạn có thể tìm thấy một số điểm đáng chú ý. Giá trị của thuật toán knapsack phụ thuộc vào hai yếu tố:

  1. Có bao nhiêu gói đang được xem xét
  2. Trọng lượng còn lại mà knapsack có thể lưu trữ.

Do đó, bạn có hai số lượng biến.

Với lập trình động, bạn có thông tin hữu ích:

  1. hàm mục tiêu sẽ phụ thuộc vào hai đại lượng biến đổi
  2. bảng tùy chọn sẽ là bảng 2 chiều.

Nếu gọi B[i][j] là giá trị tối đa có thể bằng cách chọn trong các gói {1, 2, …, i} với giới hạn trọng lượng j.

  • Giá trị tối đa khi được chọn trong n gói với giới hạn trọng lượng M là B[n][M]. Nói cách khác: Khi có các gói i để lựa chọn, B [i][j] là trọng lượng tối ưu khi trọng lượng tối đa của knapsack là j.
  • Trọng lượng tối ưu luôn nhỏ hơn hoặc bằng trọng lượng tối đa: B [i][j] ≤ j.

Ví dụ: B[4][10] = 8. Điều đó có nghĩa là trong trường hợp tối ưu, tổng trọng lượng của các gói được chọn là 8, khi có 4 gói đầu tiên để lựa chọn (gói thứ 1 đến thứ 4) và trọng lượng tối đa của bao bì là 10. Không nhất thiết phải chọn cả 4 mục.

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

Input, bạn xác định:

  • W[i], V[i] lần lượt là trọng lượng và giá trị của gói i, trong đó i {1, …, n}.
  • M là trọng lượng tối đa mà túi xách có thể mang theo.

Trong trường hợp chỉ đơn giản là chỉ có 1 gói để lựa chọn. Bạn tính toán B [1][j] cho mỗi j: có nghĩa là trọng lượng tối đa của ≥ trọng lượng của gói 1

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

Với giới hạn trọng lượng j, cá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, B[i][j] là giá trị tối đa có thể bằng cách chọn giữa 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 gói i được chọn (tất nhiên chỉ xem 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ị tối đa có thể thu được bằng cách chọn giữa các gói {1, 2, …, i – 1} với giới hạn trọng lượng (j – W [i]). Đó là, về giá trị bạn có:
B[i][j] = V[i] + B[i – 1][j – W[i]]

Due to the creation of B[i][j], which is the maximum possible value, B[i][j] will be the max of the above 2 values.

Basis of Dynamic Programming

So, you have to consider if it is better to choose package i or not. From there you have the recursive formula as follows:

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

It is easy to see B[0][j] = maximum value possible by selecting from 0 package = 0.

Calculate the Table of Options

You build a table of options based on the above recursive formula. To check if the results are correct (if not exactly, you rebuild the objective function B[i][j]). Through the creation of the objective function B[i][j] and the table of options, you will orient the tracing.

Table of options B includes n + 1 lines, M + 1 columns,

  • Firstly, filled with the basis of dynamic programming: Line 0 includes all zeros.
  • Using recursive formulas, use line 0 to calculate line 1, use line 1 to calculate line 2, etc. … until all lines are calculated.

Vấn đề Knapsack là gì?
Vấn đề Knapsack là gì?

Trace

When calculating the table of options, you are interested in B[n][M] which is the maximum value obtained when selecting in all n packages with the weight limit M.

  • If B[n][M] = B[n – 1][M] then package n is not selected, you trace B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M], you notice that the optimal selection has the package n and trace B[n – 1][M – W[n]].

Continue to trace until reaching row 0 of the table of options.

Algorithm to Look Up the Table of Options to Find the Selected Packages

Lưu ý: Nếu B[i][j] = B[i – 1][j], 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 đưa vào bao bì.

Các bước truy tìm:

  • 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, bạn tìm thấy 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, hãy chuyển sang bước 2, nếu không hãy chuyển sang bước 4
  • Bước 4: Dựa trên bảng tùy chọn để in các gói đã chọn.

Mã Java

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--;
	}
}
Hàm knapsackDyProg() trong Java

Giải thích về mã Knapsack:

  1. Tạo bảng B[][]. Đặt giá trị mặc định cho mỗi ô là 0.
  2. Xây dựng bảng B[][] theo cách từ dưới lên. Tính bảng tùy chọn với công thức truy xuất.
  3. Tính toán B[i][j]. Nếu bạn không chọn gói i.
  4. Sau đó đánh giá: nếu bạn chọn gói i, nó sẽ có lợi hơn sau đó đặt lại B [i][j].
  5. Theo dõi bảng từ hàng n đến hàng 0.
  6. Nếu bạn chọn gói n. Sau khi chọn gói n, chỉ có thể thêm trọng lượng M – W [n – 1].

Trong hướng dẫn này, bạn có hai ví dụ. Dưới đâ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