ในปัญหานี้ เราได้รับค่าจำนวนเต็มสามค่า W, n, m ซึ่งแสดงถึงความยาวของผนัง W ขนาดของชั้นวาง n และ m งานของเราคือ สร้างโปรแกรมเพื่อแก้ปัญหาชั้นวางที่เหมาะสม .
เราจำเป็นต้องหาวิธีจัดวางชั้นวางให้พอดีเพื่อให้มีพื้นที่เหลือสำหรับชั้นวางหลังการจัดวางให้เหลือน้อยที่สุด ข้อจำกัดรองขณะแก้ไขคือต้นทุนในการผลิต ชั้นวางขนาดใหญ่จะคุ้มค่ากว่า ดังนั้นเราจึงต้องให้ความสำคัญเป็นอันดับแรก
ผลลัพธ์ควรอยู่ในรูปแบบต่อไปนี้
จำนวนชั้น n ชั้น จำนวน ชั้น ขนาด m พื้นที่ว่าง
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: W = 12, n = 5, m = 3 Output: 0 4 0
คำอธิบาย
ในที่นี้ เราจะใส่ชั้นวางขนาด 4, 3 ชั้นในผนังได้พอดี
ซึ่งจะทำให้ความยาวรวม =4*3 =12
ดังนั้นความยาวในผนังจะไม่เหลือหลังจากติดตั้ง
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการใช้กำลังเดรัจฉานซึ่งก็คือการตรวจสอบชุดชั้นวางที่เหมาะสมในผนังและหาชั้นวางที่ลดหรือขจัดความยาวของพื้นที่ในผนัง สำหรับงานรอง เราจะเริ่มด้วยการใส่หมัดชั้นที่ยาวกว่าให้พอดี ซึ่งจะให้ความสำคัญกับงานชิ้นที่ใหญ่กว่า เราจะดูว่าชุดค่าผสมใดให้ผลลัพธ์ขั้นต่ำกับชั้นวางขนาดใหญ่สูงสุดที่เป็นไปได้สำหรับโซลูชันที่เหมาะสมที่สุด
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
void solveFittingShelves(int wall, int m, int n){
int numM = 0, numN = 0, minSpaceLeft = wall;
int p = wall/m, q = 0, rem = wall%m;
numM = p;
numN = q;
minSpaceLeft = rem;
while (wall >= n) {
q += 1;
wall = wall - n;
p = wall / m;
rem = wall % m;
if (rem <= minSpaceLeft) {
numM = p;
numN = q;
minSpaceLeft = rem;
}
}
cout<<numM<<" "<<numN<<" "<<minSpaceLeft<<endl;
}
int main(){
int W = 29, m = 3, n = 9;
cout<<"Length of wall : "<<W<<endl;
cout<<"Length of shelves : "<<m<<"\t"<<n<<endl;
cout<<"Optimal Shelves fitting : ";
solveFittingShelves(W, m, n);
return 0;
} ผลลัพธ์
Length of wall : 29 Length of shelves : 3 9 Optimal Shelves fitting : 0 3 2
