Trong bài toán này, chúng ta được đưa ra ba giá trị nguyên W, n, m biểu thị chiều dài của bức tường W, kích thước của kệ n và m. Nhiệm vụ của chúng tôi là Tạo một chương trình để giải quyết vấn đề lắp kệ .
Chúng ta cần phải tìm cách để lắp kệ sao cho không gian còn lại của kệ trang bị sau khi trang bị được giảm thiểu. Một trở ngại thứ hai trong khi giải quyết là chi phí sản xuất, các kệ lớn hơn sẽ tiết kiệm chi phí hơn, do đó, chúng tôi cần ưu tiên cho chúng.
Đầu ra phải ở dạng sau,
Số lượng kệ kích thước n số lượng kệ kích thước m còn lại
Hãy lấy một ví dụ để hiểu vấn đề
Input: W = 12, n = 5, m = 3 Output: 0 4 0
Giải thích
Tại đây, chúng tôi có thể lắp đúng 4, 3 kệ có kích thước vào tường.
Điều này sẽ làm cho tổng chiều dài =4 * 3 =12
Vì vậy, không có chiều dài tường nào còn lại sau khi lắp.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề này là sử dụng cách tiếp cận brute force whichis bằng cách kiểm tra từng sự kết hợp có thể có của các giá phù hợp trong tường và tìm những giá để giảm thiểu hoặc loại bỏ chiều dài không gian trong tường. Đối với nhiệm vụ thứ yếu, chúng tôi sẽ bắt đầu với việc lắp nắm tay giá đỡ có chiều dài lớn hơn, điều này sẽ ưu tiên cho nhiệm vụ lớn hơn. Chúng tôi sẽ xem sự kết hợp nào cho kết quả tối thiểu với giá trị lớn nhất có thể để có giải pháp tối ưu.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
Length of wall : 29 Length of shelves : 3 9 Optimal Shelves fitting : 0 3 2