सी ++ में फिटिंग शेल्फ समस्या

इस समस्या में, हमें तीन पूर्णांक मान 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