সি++ এ তাক লাগানোর সমস্যা

এই সমস্যায়, আমাদের তিনটি পূর্ণসংখ্যার মান দেওয়া হয়েছে 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