이 문제에서 벽의 길이 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