บทนำ
มีเชือก N เส้น ที่มีความยาวกำหนด ต้องการเชื่อมต่อพวกมัน ต้นทุนในการเชื่อมเชือกหนึ่งเส้นกับอีกเส้นหนึ่ง คือผลรวมของความยาวของพวกมัน เป้าหมายคือเชื่อมเชือก N เส้นด้วยต้นทุนต่ำสุด
ปัญหานี้แก้ได้ด้วย Heap Tree (กอง) เราจะสร้าง Min Heap เพื่อใส่ความยาวต่างๆ ทั้งหมด แล้วนำ Minimum และ Second Minimum ออกจาก Min Heap เชื่อมพวกมันแล้วใส่กลับเข้า Heap Tree อีกครั้ง เมื่อ Heap เหลือเพียงหนึ่งอิลิเมนต์ เราสามารถหยุดกระบวนการและได้เชือกที่เชื่อมต่อด้วยต้นทุนต่ำสุด
อินพุตและเอาต์พุต
Input: ความยาวของเชือก: {4, 3, 2, 6, 5, 7, 12}
Output: ต้นทุนรวมต่ำสุด: 103
อัลกอริทึม
findMinCost(array, n)
Input: รายการความยาวเชือก, จำนวนรายการในลิสต์
Output: ต้นทุนต่ำสุดในการตัด
Begin
minCost := 0
เติม priority queue ด้วยอิลิเมนต์ของอาเรย์ (ค่าที่มากกว่ามี priority สูงกว่า)
while queue ไม่ว่าง, do
item1 := ดึงไอเทมจาก queue และลบออกจาก queue
item2 := ดึงไอเทมจาก queue และลบออกจาก queue
minCost := minCost + item1 + item2
เพิ่ม (item1 + item2) เข้า queue
done
return minCost
End
ตัวอย่างโค้ด (C++)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int findMinimumCost(int arr[], int n) {
// priority queue ตั้งค่าให้ค่าที่มากกว่ามี priority สูงกว่า
priority_queue, greater> queue(arr, arr+n);
int minCost = 0;
while (queue.size() > 1) {
// เมื่อ queue มีมากกว่าหนึ่งอิลิเมนต์
int item1 = queue.top(); // item1 คืออิลิเมนต์สั้นที่สุด
queue.pop();
int item2 = queue.top(); // item2 ใหญ่กว่า item1 แต่น้อยกว่าอื่น
queue.pop();
minCost += item1 + item2; // เชื่อมเชือกและเพิ่มเข้า queue
queue.push(item1 + item2);
}
return minCost;
}
int main() {
int ropeLength[] = {4, 3, 2, 6, 5, 7, 12};
int n = 7;
cout << "Total minimum cost: " << findMinimumCost(ropeLength, n);
}
ผลลัพธ์
Total minimum cost: 103
