সমস্যা বিবরণ
দেওয়ালের দৈর্ঘ্য W এবং দুটি শেলফের আকার n, m দেওয়া আছে। শেলফগুলো এভাবে ফিট করতে হবে যেন খালি জায়গা ন্যূনতম হয়। বড় শেলফে প্রাধান্য দেওয়া হবে।
উদাহরণ
ইনপুট: W = 12, n = 5, m = 3 আউটপুট: 0 4 0 ব্যাখ্যা: ৪টি ৩-সাইজ শেলফ দিয়ে ১২ দৈর্ঘ্য ঠিক পূরণ হয়।
সমাধানের পদ্ধতি
ব্রুট ফোর্স: বড় শেলফকে প্রাধান্য দিয়ে সব সম্ভাব্য কম্বিনেশন চেক করে ন্যূনতম খালি জায়গা বের করা।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void solveFittingShelves(int wall, int m, int n) {
int numM=0, numN=0, minLeft=wall;
int p=wall/m, q=0, rem=wall%m;
numM=p; numN=q; minLeft=rem;
while(wall >= n){
q++; wall -= n;
p = wall/m; rem = wall%m;
if(rem <= minLeft){
numM=p; numN=q; minLeft=rem;
}
}
cout << numM << " " << numN << " " << minLeft;
}
int main() {
int W=29, m=3, n=9;
cout << "Optimal: "; solveFittingShelves(W,m,n);
return 0;
}
আউটপুট
Optimal: 0 3 2
