इस समस्या में, हमें तीन पूर्णांक मान W, n, m दिए गए हैं जो दीवार की लंबाई W, शेल्फ के आकार n, और m को दर्शाते हैं। हमारा कार्य शेल्फ फिटिंग समस्या को हल करने के लिए एक प्रोग्राम बनाना है।
हमें शेल्फ को इस तरह फिट करने का तरीका ढूंढना है कि शेल्फ फिट करने के बाद बची हुई जगह न्यूनतम हो। हल करते समय एक द्वितीयक प्रतिबंध लागत है, बड़े शेल्फ अधिक लागत-प्रभावी हैं इसलिए हमें उन्हें प्राथमिकता देनी होगी।
आउटपुट निम्न रूप में होना चाहिए,
n आकार के शेल्फ की संख्या m आकार के शेल्फ की संख्या बची हुई जगह
समस्या को समझने के लिए एक उदाहरण लेते हैं
इनपुट: W = 12, n = 5, m = 3 आउटपुट: 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<<"दीवार की लंबाई : "<<W<<endl; cout<<"शेल्फ की लंबाई : "<<m<<"\t"<<n<<endl; cout<<"इष्टतम शेल्फ फिटिंग : "; solveFittingShelves(W, m, n); return 0; } आउटपुट
दीवार की लंबाई : 29 शेल्फ की लंबाई : 3 9 इष्टतम शेल्फ फिटिंग : 0 3 2
