0/1 แก้ไขปัญหากระเป๋าเป้สะพายหลังโดยใช้ตัวอย่างการเขียนโปรแกรมแบบไดนามิก

ปัญหากระเป๋าเป้สะพายหลังคืออะไร?

ปัญหากระเป๋าเป้สะพายหลัง อัลกอริธึมเป็นปัญหาที่มีประโยชน์มากในเชิงผสม ในซุปเปอร์มาร์เก็ตไม่มีพัสดุ (n ≤ 100) พัสดุ i มีน้ำหนัก W[i] ≤ 100 และค่า V[i] ≤ 100 โจรบุกเข้าไปในซุปเปอร์มาร์เก็ต ขโมยไม่สามารถบรรทุกน้ำหนักเกิน M (M ≤ 100) ). ปัญหาที่ต้องแก้ไขคือ แพ็คเกจไหนที่โจรจะเอาไปให้ได้มูลค่าสูงสุด?

Input:

น้ำหนักสูงสุด M และจำนวนบรรจุภัณฑ์ n
อาร์เรย์ของน้ำหนัก W[i] และค่าที่สอดคล้องกัน V[i]

Output:

เพิ่มมูลค่าสูงสุดและน้ำหนักที่สอดคล้องกันในความจุ
ซึ่งพัสดุที่ขโมยจะเอาไป

อัลกอริธึม Knapsack สามารถแบ่งออกได้เป็น 2 ประเภท:

ปัญหา 0/1 เป้โดยใช้การเขียนโปรแกรมแบบไดนามิก ในประเภทอัลกอริธึม Knapsack นี้ แต่ละแพ็คเกจสามารถรับหรือไม่รับได้ นอกจากนี้ โจรไม่สามารถรับพัสดุที่นำมาเป็นจำนวนเศษๆ หรือหยิบพัสดุมากกว่าหนึ่งครั้งได้ ประเภทนี้สามารถแก้ไขได้โดย Dynamic Programming Approach
อัลกอริธึมปัญหา Fractional Knapsack- ประเภทนี้สามารถแก้ไขได้ด้วย Greedy Strategy

วิธีแก้ปัญหากระเป๋าเป้สะพายหลังโดยใช้การเขียนโปรแกรมแบบไดนามิกพร้อมตัวอย่าง

ในกลยุทธ์การแบ่งแยกและพิชิต คุณแบ่งปัญหาที่จะแก้ไขออกเป็นปัญหาย่อย ปัญหาย่อยจะถูกแบ่งออกเป็นปัญหาย่อยเพิ่มเติม งานนั้นจะดำเนินต่อไปจนกว่าคุณจะได้รับปัญหาย่อยที่สามารถแก้ไขได้ง่าย อย่างไรก็ตามในกระบวนการแบ่งดังกล่าวคุณอาจประสบปัญหาเดียวกันหลายครั้ง

แนวคิดพื้นฐานของการเขียนโปรแกรมแบบไดนามิกของ Knapsack คือการใช้ตารางเพื่อจัดเก็บโซลูชันของปัญหาที่แก้ไขแล้ว หากคุณพบปัญหาที่แก้ไขแล้วอีกครั้ง คุณเพียงแค่นำโซลูชันนั้นมาใช้ในตารางโดยไม่ต้องแก้ไขซ้ำอีก ดังนั้นอัลกอริทึมที่ออกแบบโดยการเขียนโปรแกรมแบบไดนามิกจึงมีประสิทธิภาพมาก

ในการแก้ไขปัญหาด้วยการเขียนโปรแกรมแบบไดนามิก คุณต้องดำเนินการดังต่อไปนี้:

ค้นหาวิธีแก้ไขปัญหาย่อยที่เล็กที่สุด
ค้นหาสูตร (หรือกฎ) เพื่อสร้างวิธีแก้ปัญหาย่อยผ่านวิธีแก้ปัญหาย่อยแม้แต่ปัญหาย่อยที่เล็กที่สุด
สร้างตารางที่เก็บแนวทางแก้ไขปัญหาย่อย จากนั้นคำนวณวิธีแก้ปัญหาย่อยตามสูตรที่พบแล้วบันทึกลงตาราง
จากปัญหาย่อยที่แก้ไขแล้ว คุณจะพบวิธีแก้ไขปัญหาเดิม

วิเคราะห์ปัญหากระเป๋าเป้สะพายหลัง 0/1

เมื่อวิเคราะห์ปัญหา 0/1 Knapsack โดยใช้การเขียนโปรแกรมแบบไดนามิก คุณจะพบจุดที่เห็นได้ชัดเจน ค่าของอัลกอริธึมเป้หลังขึ้นอยู่กับปัจจัยสองประการ:

พิจารณากี่แพ็คเกจ
น้ำหนักที่เหลือซึ่งเป้สามารถจัดเก็บได้

ดังนั้น คุณมีปริมาณที่แปรผันได้สองปริมาณ

ด้วยการเขียนโปรแกรมแบบไดนามิก คุณจะได้รับข้อมูลที่เป็นประโยชน์:

ฟังก์ชันวัตถุประสงค์จะขึ้นอยู่กับปริมาณตัวแปรสองตัว
ตารางตัวเลือกจะเป็นตาราง 2 มิติ

หากการเรียก B[i][j] เป็นค่าสูงสุดที่เป็นไปได้โดยการเลือกในแพ็คเกจ {1, 2, …, i} โดยมีขีดจำกัดน้ำหนัก j

ค่าสูงสุดเมื่อเลือกในแพ็คเกจ n ที่มีขีดจำกัดน้ำหนัก M คือ B[n][M] กล่าวอีกนัยหนึ่ง: เมื่อมีแพ็คเกจ i ให้เลือก B[i][j] คือน้ำหนักที่เหมาะสมที่สุดเมื่อน้ำหนักสูงสุดของกระเป๋าเป้สะพายหลังคือ j
น้ำหนักที่เหมาะสมที่สุดจะน้อยกว่าหรือเท่ากับน้ำหนักสูงสุดเสมอ: B[i][j] ≤ j

ตัวอย่างเช่น: B[4][10] = 8 หมายความว่าในกรณีที่เหมาะสมที่สุด น้ำหนักรวมของพัสดุที่เลือกคือ 8 เมื่อมีพัสดุภัณฑ์แรกให้เลือก 4 พัสดุ (พัสดุที่ 1 ถึง 4) และน้ำหนักสูงสุด ของเป้เป็น 10 ครับ ไม่จำเป็นต้องเลือกทั้ง 4 รายการครับ

สูตรคำนวณ B[i][j]

อินพุต คุณกำหนด:

W[i], V[i] จะเป็นน้ำหนักและมูลค่าของบรรจุภัณฑ์ i โดยที่ i {1, …, น}
M คือน้ำหนักสูงสุดที่กระเป๋าเป้สามารถบรรทุกได้

กรณีให้เลือกเพียง 1 แพ็คเกจเท่านั้น คุณคำนวณ B[1][j] สำหรับทุก ๆ j: ซึ่งหมายถึงน้ำหนักสูงสุดของเป้ ≥ น้ำหนักของบรรจุภัณฑ์ใบที่ 1

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

ด้วยขีดจำกัดน้ำหนัก j การเลือกที่เหมาะสมที่สุดระหว่างแพ็คเกจ {1, 2, …, i – 1, i} เพื่อให้มีค่ามากที่สุดจะมีความเป็นไปได้สองประการ:

หากไม่ได้เลือกแพ็คเกจ i B[i][j] จะเป็นค่าสูงสุดที่เป็นไปได้โดยการเลือกระหว่างแพ็คเกจ {1, 2, …, i – 1} โดยมีขีดจำกัดน้ำหนักอยู่ที่ j คุณมี:

B[i][j] = B[i – 1][j]

หากเลือกแพ็คเกจ i (แน่นอนว่าพิจารณาเฉพาะกรณีนี้เมื่อ W[i] ≤ j) ดังนั้น B[i][j] จะเท่ากับค่า V[i] ของแพ็คเกจ i บวกกับค่าสูงสุดที่สามารถรับได้โดยการเลือกระหว่าง แพ็คเกจ {1, 2, …, i – 1} พร้อมขีดจำกัดน้ำหนัก (j – W[i]) นั่นคือในแง่ของมูลค่าที่คุณมี:

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

เนื่องจากการสร้าง B[i][j] ซึ่งเป็นค่าสูงสุดที่เป็นไปได้ B[i][j] จะเป็นค่าสูงสุดจาก 2 ค่าข้างต้น

พื้นฐานของการเขียนโปรแกรมแบบไดนามิก

ดังนั้นคุณต้องพิจารณาว่าควรเลือกแพ็คเกจ i ดีกว่าหรือไม่ จากนั้นคุณจะได้สูตรแบบเรียกซ้ำดังนี้:

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

ดูง่ายๆ B[0][j] = ค่าสูงสุดที่เป็นไปได้โดยเลือกจาก 0 แพ็คเกจ = 0

คำนวณตารางตัวเลือก

คุณสร้างตารางตัวเลือกตามสูตรแบบเรียกซ้ำข้างต้น เพื่อตรวจสอบว่าผลลัพธ์ถูกต้องหรือไม่ (หากไม่ตรง คุณจะต้องสร้างฟังก์ชันวัตถุประสงค์ B[i][j] ใหม่) ด้วยการสร้างฟังก์ชันวัตถุประสงค์ B[i][j] และตารางตัวเลือก คุณจะกำหนดทิศทางการติดตาม

ตารางตัวเลือก B ประกอบด้วย n + 1 บรรทัด, M + 1 คอลัมน์

ประการแรก เต็มไปด้วยพื้นฐานของการเขียนโปรแกรมแบบไดนามิก: บรรทัด 0 มีศูนย์ทั้งหมด
การใช้สูตรแบบเรียกซ้ำ ใช้บรรทัด 0 เพื่อคำนวณบรรทัดที่ 1 ใช้บรรทัดที่ 1 เพื่อคำนวณบรรทัดที่ 2 ฯลฯ … จนกว่าจะคำนวณทุกบรรทัด

ติดตาม

เมื่อคำนวณตารางตัวเลือก คุณสนใจ B[n][M] ซึ่งเป็นค่าสูงสุดที่ได้รับเมื่อเลือกในแพ็คเกจ n ทั้งหมดที่มีขีดจำกัดน้ำหนัก M

If B[n][M] = B[n – 1][M] ดังนั้นแพ็คเกจ n จะไม่ถูกเลือก คุณติดตาม B[n – 1][M]
If B[n][M] ≠ B[n – 1][M]คุณจะสังเกตเห็นว่าการเลือกที่เหมาะสมที่สุดมีแพ็คเกจ n และการติดตาม B[n – 1][M – W[n]]

ติดตามต่อไปจนถึงแถว 0 ของตารางตัวเลือก

อัลกอริทึมในการค้นหาตารางตัวเลือกเพื่อค้นหาแพ็คเกจที่เลือก

หมายเหตุ: ถ้า B[i][j] = B[i – 1][j] แพ็กเกจ i จะไม่ถูกเลือก B[n][W] คือมูลค่ารวมที่เหมาะสมที่สุดของบรรจุภัณฑ์ที่ใส่ไว้ในกระเป๋าเป้สะพายหลัง

ขั้นตอนในการติดตาม:

ขั้นตอนที่ 1: เริ่มต้นจาก i = n, j = M
ขั้นตอนที่ 2: ดูในคอลัมน์ j จากด้านล่างสุด คุณจะพบว่าเส้น i เป็น B[i][j] > B[i – 1][j] ทำเครื่องหมายแพ็คเกจที่เลือก i: เลือก [i] = true;
ขั้นตอนที่ 3: j = B[i][j] – W[i] หาก j > 0 ให้ไปที่ขั้นตอนที่ 2 มิฉะนั้น ให้ไปที่ขั้นตอนที่ 4
ขั้นตอนที่ 4: ขึ้นอยู่กับตารางตัวเลือกในการพิมพ์แพ็คเกจที่เลือก

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--;
	}
}

คำอธิบายของรหัสกระเป๋าเป้สะพายหลัง:

สร้างตาราง B[][] ตั้งค่าเริ่มต้นสำหรับแต่ละเซลล์คือ 0
สร้างตาราง B[] ในลักษณะจากล่างขึ้นบน คำนวณตารางตัวเลือกด้วยสูตรการดึงข้อมูล
คำนวณ B[i][j] หากไม่เลือกแพ็คเกจ i.
จากนั้นประเมิน: หากคุณเลือกแพ็คเกจ i มันจะมีประโยชน์มากกว่า จากนั้นรีเซ็ต B[i][j]
ติดตามตารางจากแถว n ถึงแถว 0
หากคุณเลือกแพ็คเกจ n. เมื่อเลือกแพ็คเกจ n แล้ว จะสามารถเพิ่มได้เฉพาะน้ำหนัก M – W[n – 1] เท่านั้น

ในบทช่วยสอนนี้ คุณมีสองตัวอย่าง นี่คือโค้ด Java เพื่อรันโปรแกรมด้านบนพร้อมสองตัวอย่าง:

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);
}

คุณมีผลลัพธ์:

ตัวอย่างแรก:

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

ตัวอย่างที่สอง:

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