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

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

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

Input:

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

Output:

• มูลค่ารวมสูงสุดที่สามารถได้รับภายในขีดจำกัดความจุ
• ชุดของสิ่งของที่โจรควรหยิบไปอย่างแม่นยำ

อัลกอริทึม Knapsack แบ่งออกเป็นสองรูปแบบที่รู้จักกันดี:

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

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

การแบ่งและพิชิต (Divide-and-conquer) คือการแบ่งปัญหาใหญ่ให้เป็นปัญหาย่อย แล้วแบ่งต่อไปเรื่อยๆ จนกว่าแต่ละปัญหาย่อยจะง่าย อย่างไรก็ตาม การเรียกซ้ำแบบธรรมดา มักจะแก้ปัญหาย่อยเดียวกันซ้ำหลายครั้งและเป็นการสิ้นเปลืองเวลา

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

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

ในการออกแบบโซลูชันการเขียนโปรแกรมแบบไดนามิก คุณต้องทำตามสี่ขั้นตอนดังนี้:

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

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

ค่าที่เหมาะสมที่สุดขึ้นอยู่กับปัจจัยอิสระสองประการ:

1. มีแพ็กเกจกี่แพ็กเกจที่ยังอยู่ระหว่างการพิจารณา
2. น้ำหนักที่เหลือที่กระเป๋าเป้ยังสามารถรับได้

เนื่องจากฟังก์ชันเป้าหมายขึ้นอยู่กับปริมาณสองอย่าง ตารางตัวเลือกจึงต้องเป็นตารางสองมิติ ให้ B[i][j] ระบุค่าสูงสุดเมื่อเลือกแพ็คเกจ {1, …, i} โดยมีน้ำหนักจำกัด j

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

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

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

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

กรณีพื้นฐานที่มีแพ็คเกจเดียว: สำหรับความจุ j ≥ W[1] ทุกค่า:

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

โดยทั่วไปแล้ว ให้ตัดสินใจว่าจะรวมแพ็คเกจ i ไว้ในความจุ j หรือไม่:

• ถ้าแพ็คเกจ i คือ ข้ามB[i][j] เท่ากับค่าที่ดีที่สุดโดยใช้แพ็กเกจ {1, …, i-1} ภายใต้ความจุ j:

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

• ถ้าแพ็คเกจ i คือ นำ (อนุญาตเฉพาะเมื่อ W[i] ≤ j เท่านั้น) B[i][j] เท่ากับ V[i] บวกกับค่าที่ดีที่สุดจากแพ็กเกจ {1, …, i-1} ภายใต้ความจุ j – W[i]:

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

เลือกผู้สมัครที่มีค่าตัวใหญ่กว่าในสองคนนั้น

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

เมื่อรวมทั้งสองกรณีเข้าด้วยกัน จะได้การเกิดซ้ำอย่างสมบูรณ์:

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

กรณีพื้นฐานคือ B[0][j] = 0 สำหรับทุก j เพราะแพ็กเกจศูนย์จะให้ค่าเป็นศูนย์ไม่ว่าจะมีความจุเท่าใดก็ตาม

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

สร้าง B โดยใช้ความสัมพันธ์เวียนเกิด เมื่อเติม B เสร็จแล้ว ตารางเดียวกันนี้จะขับเคลื่อนต่อไป trace-back ที่สร้างแพ็กเกจที่เลือกขึ้นใหม่ ตาราง B มี n + 1 แถวและ M + 1 คอลัมน์:

• แถวที่ 0 คือกรณีพื้นฐาน ซึ่งเต็มไปด้วยเลขศูนย์
• ใช้แถวที่ 0 ในการคำนวณแถวที่ 1 ใช้แถวที่ 1 ในการคำนวณแถวที่ 2 และทำเช่นนี้ต่อไปจนกว่าจะเสร็จสิ้นแถวที่ n

ตารางตัวเลือก

Trace

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

• If B[n][M] = B[n-1][M]แพ็คเกจ n ไม่ได้รับการเลือก ดังนั้นให้ดำเนินการต่อ tracing จาก B[n-1][M]
• If B[n][M] ≠ B[n-1][M]เลือกแพ็คเกจ n แล้ว ดังนั้นให้ดำเนินการต่อ tracing จาก B[n-1][M – W[n]]

ทำซ้ำไปเรื่อยๆ จนกว่าจะถึงแถวที่ 0 ของตาราง

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

หมายเหตุ: เมื่อใดก็ตามที่ B[i][j] = B[i-1][j]แพ็คเกจ i ไม่ได้รับการเลือก ค่า B[n][M] คือมูลค่ารวมที่เหมาะสมที่สุดที่บรรจุอยู่ในกระเป๋าเป้

ขั้นตอนสำหรับ tracโดยการเลือกแพ็กเกจที่เลือกไว้:

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

Java Code

ดังต่อไปนี้ Java เมธอดจะเติม B[][] จากล่างขึ้นบน พิมพ์ตารางเพื่อตรวจสอบ แล้วจึง tracคือแพ็กเกจที่เลือกไว้

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

ฟังก์ชัน knapsackDyProg() ใน Java

คำอธิบายของรหัส:

1. จัดสรรตาราง B[][] และกำหนดค่าเริ่มต้นให้กับทุกเซลล์เป็น 0
2. เติม B[][] จากล่างขึ้นบนโดยใช้ความสัมพันธ์เวียนเกิดจากส่วนก่อนหน้า
3. เริ่มต้นแต่ละเซลล์ด้วยค่า “ข้ามแพ็กเกจ i” B[i-1][j].
4. หากการเลือกแพ็กเกจ i เป็นไปได้และให้ผลลัพธ์ที่ดีกว่าอย่างเห็นได้ชัด ให้เขียนทับค่าในเซลล์นั้น
5. Trace คัดลอกรายการที่เลือกจากแถว n กลับไปยังแถว 0
6. ทุกครั้งที่เลือกแพ็คเกจ n ให้ลดความจุที่เหลืออยู่ลงตาม W[n-1].

หมายเหตุการแก้ไข: พารามิเตอร์ที่กลายพันธุ์ของส่วนย่อยดั้งเดิม M ขณะที่ยังคงอ่านอยู่ B[n][M]เวอร์ชันที่ปลอดภัยกว่าด้านบนใช้เคอร์เซอร์แยกต่างหาก j สำหรับ trace.

การขอ Java ไดรเวอร์รันอัลกอริทึมกับตัวอย่างที่ใช้งานได้สองตัวอย่าง:

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

ผลลัพธ์สำหรับตัวอย่างแรก:

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

ความซับซ้อนของเวลาและพื้นที่ของกระเป๋าเป้สะพายหลัง 0/1

• ความซับซ้อนเชิงเวลา: O(n · M) — ลูปซ้อนกันสองลูปจะกวาดรายการ n รายการไปทั่วสถานะความจุ M+1
• ความซับซ้อนของพื้นที่: O(n · M) สำหรับตารางทั้งหมด สามารถลดรูปเป็น O(M) ได้โดยใช้ keeping เฉพาะแถวก่อนหน้าเมื่อ tracไม่จำเป็นต้องส่งอีเมลตอบกลับ

ระยะเวลาการทำงานคือ พหุนามเทียม: มีค่าเป็นพหุนามเมื่อเทียบกับค่าของ M แต่มีค่าเป็นเลขชี้กำลังเมื่อเทียบกับจำนวนบิตที่ใช้ในการเข้ารหัส M นั่นคือเหตุผลที่ปัญหา 0/1 Knapsack ยังคงเป็นปัญหา NP-hard แม้ว่าการเขียนโปรแกรมเชิงพลวัต (Dynamic Programming) จะมีประสิทธิภาพในทางปฏิบัติก็ตาม

การประยุกต์ใช้ปัญหาเป้สะพายหลัง 0/1

• การขนถ่ายสินค้า การบรรจุลงตู้คอนเทนเนอร์ และการคัดแยกสินค้าในคลังสินค้าภายใต้ข้อจำกัดด้านน้ำหนัก
• การจัดสรรงบประมาณให้กับโครงการลงทุนที่มีต้นทุนคงที่และผลตอบแทนที่คาดหวัง
• ปัญหาการตัดเฉือนในกระบวนการผลิตที่ไม่สามารถแยกชิ้นส่วนแต่ละชิ้นออกจากกันได้
• ระบบการเข้ารหัสลับ เช่น Merkle-Hellman ที่สร้างขึ้นบนพื้นฐานของความยากระดับกระเป๋าเป้ (knapsack hardness)
• การจัดตารางเวลาภายใต้ข้อจำกัดด้านทรัพยากรในระบบคลาวด์และการจัดวางงานของ CPU
• การเลือกคุณลักษณะในแมชชีนเลิร์นนิงภายใต้งบประมาณคุณลักษณะที่จำกัด

คำถามที่พบบ่อย