แนวคิด
สมมติว่ามีกระดานที่มีความยาว p และความกว้าง q เราต้องแบ่งกระดานนี้ออกเป็นสี่เหลี่ยม p*q เพื่อให้ค่าใช้จ่ายในการทำลายน้อยที่สุด สำหรับบอร์ดนี้ จะมีการลดราคาสำหรับแต่ละขอบ โดยสรุป เราต้องการเลือกลำดับการตัดดังกล่าวซึ่งจะช่วยลดต้นทุนได้
ตัวอย่าง
ด้วยความเคารพของกระดานด้านบน วิธีที่เหมาะสมที่สุดในการตัดเป็นสี่เหลี่ยมจัตุรัสคือ −
ต้นทุนขั้นต่ำรวมในกรณีข้างต้นคือ 65 คำนวณแล้วนำไปประยุกต์ใช้ตามขั้นตอนต่อไปนี้
Initial Value : Total_cost = 0 Total_cost = Total_cost + edge_cost * total_pieces Cost 5 Horizontal cut Cost = 0 + 5*1 = 5 Cost 5 Vertical cut Cost = 5 + 5*2 = 15 Cost 4 Vertical cut Cost = 15 + 4*2 = 23 Cost 3 Horizontal cut Cost = 23 + 3*3 = 32 Cost 3 Vertical cut Cost = 32 + 3*3 = 41 Cost 2 Horizontal cut Cost = 41 + 2*4 = 49 Cost 2 Vertical cut Cost = 49 + 2*4 = 57 Cost 2 Vertical cut Cost = 57 + 2*4 = 65
วิธีการ
ปัญหาประเภทนี้สามารถแก้ไขได้โดยใช้วิธีการโลภ หาก S ดำเนินการกับต้นทุนทั้งหมด ดังนั้น S =b1x1 + b2x2 … + bkxk โดยที่ xi ถือเป็นต้นทุนของการตัดขอบบางค่า และค่า bi เป็นค่าสัมประสิทธิ์ที่สอดคล้องกัน ค่าสัมประสิทธิ์ bi จะถูกกำหนดโดยจำนวนการตัดทั้งหมดที่เราได้แข่งขันกัน xi เมื่อสิ้นสุดกระบวนการตัด
เราควรสังเกตว่าผลรวมของสัมประสิทธิ์เป็นค่าคงที่เสมอ ดังนั้นเราต้องการคำนวณการแจกแจงของ bi ที่หาได้ โดยที่ S มีค่าน้อยที่สุด ในการดำเนินการดังกล่าว เราลดขอบด้านต้นทุนที่ใหญ่ที่สุดให้สำเร็จโดยเร็วที่สุด ซึ่งจะไปถึง S ที่เหมาะสมที่สุด หากเราพบหลายขอบที่มีต้นทุนเท่ากัน เราสามารถลบหรือตัดส่วนใดส่วนหนึ่งออกก่อน
โปรแกรม C++
ต่อไปนี้คือโซลูชันที่ใช้แนวทางข้างต้น ก่อนอื่นเราจัดเรียงต้นทุนการตัดขอบในลำดับย้อนกลับ จากนั้นเราวนลูปจากต้นทุนที่สูงขึ้นไปเป็นต้นทุนที่ต่ำลงในการสร้างโซลูชันของเรา ทุกครั้งที่เราเลือกคมตัด จำนวนคู่จะเพิ่มขึ้น 1 ซึ่งจะถูกคูณในแต่ละครั้งด้วยต้นทุนการตัดคมตัดที่สอดคล้องกัน
ตัวอย่าง
// C++ program to divide a board into p*q squares
#include <bits/stdc++.h>
using namespace std;
int minimumCostOfBreaking(int X1[], int Y1[], int p, int q){
int res1 = 0;
sort(X1, X1 + p, greater<int>());
sort(Y1, Y1 + q, greater<int>());
int hzntl = 1, vert = 1;
int i = 0, j = 0;
while (i < p && j < q){
if (X1[i] > Y1[j]){
res1 += X1[i] * vert;
hzntl++;
i++;
}
else{
res1 += Y1[j] * hzntl;
vert++;
j++;
}
}
int total = 0;
while (i < p)
total += X1[i++];
res1 += total * vert;
total = 0;
while (j < q)
total += Y1[j++];
res1 += total * hzntl;
return res1;
}
int main(){
int p = 6, q = 4;
int X1[p-1] = {3, 2, 4, 2, 5};
int Y1[q-1] = {5, 2, 3};
cout << minimumCostOfBreaking(X1, Y1, p-1, q-1);
return 0;
} ผลลัพธ์
65
