각각의 용량 C에 서로 다른 가중치와 빈의 m개의 요소가 주어진 경우, 구현된 전체 빈의 수가 최소화되도록 각 요소를 빈에 할당합니다. 모든 요소의 가중치가 빈 용량보다 작다고 가정해야 합니다.
응용 프로그램
-
여러 디스크에 데이터를 저장합니다.
-
트럭과 같은 컨테이너 적재.
-
고정 길이의 라디오/TV 방송국에서 광고를 포장합니다.
-
작업 일정.
예시
Input: weight[] = {4, 1, 8, 1, 4, 2}
Bin Capacity c = 10
Output: 2
We require at least 2 bins to accommodate all elements
First bin consists {4, 4, 2} and second bin {8, 2} 하한
ceil() 함수를 사용하여 필요한 최소 빈 수에 대한 하한을 항상 계산할 수 있습니다. 하한은 다음과 같이 주어질 수 있습니다. -
-
최소 개수의 빈>=ceil ((총 중량) / (빈 용량))
-
위의 예에서 첫 번째 예의 하한은 "ceil(4 + 1 + 8 + 2 + 4 + 1)/10" =2
입니다. -
이 문제에 대해 다음과 같은 대략적인 알고리즘이 구현됩니다.
온라인 알고리즘
이러한 알고리즘은 요소가 한 번에 하나씩(알 수 없는 순서로) 도착하는 Bin Packing 문제에 대해 구현되며 다음 요소를 고려하기 전에 각각을 bin에 넣어야 합니다.
다음 맞춤 -
다음 요소를 처리할 때 마지막 요소와 동일한 빈에 맞는지 확인합니다. 그렇지 않은 경우에만 새 저장소를 구현하십시오.
다음은 이 알고리즘에 대한 C++ 응용 프로그램입니다.
// C++ program to calculate number of bins required implementing next fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to return number of bins needed implementing next fit online algorithm
int nextFit(int weight1[], int m, int C){
// Result (Count of bins) and remaining capacity in current bin are initialized.
int res = 0, bin_rem = C;
// We have to place elements one by one
for (int i = 0; i < m; i++) {
// If this element can't fit in current bin
if (weight1[i] > bin_rem) {
res++; // Use a new bin
bin_rem = C - weight1[i];
}
else
bin_rem -= weight1[i];
}
return res;
}
// Driver program
int main(){
int weight1[] = { 3, 6, 5, 8, 2, 4, 9 };
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout<< "Number of bins required in Next Fit : "
<<nextFit(weight1, m, C);
return 0;
} 출력
Number of bins required in Next Fit : 4
Next Fit은 단순한 알고리즘으로 취급됩니다. m개의 요소를 처리하기 위해 O(m) 시간과 O(1) 추가 공간만 필요합니다.
퍼스트핏-
다음 요소를 처리할 때 이전 bin을 순서대로 검사하거나 스캔하고 해당하는 첫 번째 bin에 요소를 배치합니다. 해당 시점에 요소가 기존 bin에 맞지 않으면 새 bin만 시작합니다.
예시
// C++ program to find number of bins needed implementing First Fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to return number of bins needed implementing first fit online algorithm
int firstFit(int weight1[], int m, int C){
// We have to initialize result (Count of bins)
int res = 0;
// We have to create an array to store remaining space in bins there can be maximum n bins
int bin_rem[m];
// We have to place elements one by one
for (int i = 0; i < m; i++) {
// We have to find the first bin that can accommodate weight1[i]
int j;
for (j = 0; j < res; j++) {
if (bin_rem[j] >= weight1[i]) {
bin_rem[j] = bin_rem[j] - weight1[i];
break;
}
}
// If no bin could accommodate weight1[i]
if (j == res) {
bin_rem[res] = C - weight1[i];
res++;
}
}
return res;
}
// Driver program
int main(){
int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout<< "Number of bins required in First Fit : "
<<firstFit(weight1, m, C);
return 0;
} 출력
Number of bins required in First Fit : 4
위의 First Fit 구현은 O(m2) 시간을 소비하지만 First Fit은 Self-Balancing Binary Search Tree를 구현하는 O(m log m) 시간에 사용할 수 있습니다.
베스트 핏 -
개념은 다음 항목을 가장 단단한 위치에 배치하는 것입니다. 즉, 최소한 빈 공간이 남도록 휴지통에 넣으십시오.
예시
// C++ program to calculate number of bins required implementing Best fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to returns number of bins required implementing best fit online algorithm
int bestFit(int weight1[], int m, int C){
// We have to initialize result (Count of bins)
int res = 0;
// We have to create an array to store remaining space in bins there can be maximum n bins
int bin_rem[m];
// Place elements one by one
for (int i = 0; i < m; i++){
// Find the best bin that can accomodate weight1[i]
int j;
// We have to initialize minimum space left and index of best bin
int min = C + 1, bi = 0;
for (j = 0; j < res; j++){
if (bin_rem[j] >= weight1[i] && bin_rem[j] - weight1[i] < min) {
bi = j;
min = bin_rem[j] - weight1[i];
}
}
// We create a new bin,if no bin could accommodate weight1[i],
if (min == C + 1) {
bin_rem[res] = C - weight1[i];
res++;
}
else // Assign the element to best bin
bin_rem[bi] -= weight1[i];
}
return res;
}
// Driver program
int main(){
int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout<< "Number of bins required in Best Fit : "
<<bestFit(weight1, m, C);
return 0;
} 출력
Number of bins required in Best Fit : 4
Best Fit은 Self-Balancing Binary Search Trees를 구현하는 O(m log m) 시간에도 적용될 수 있습니다.
오프라인 알고리즘
오프라인 버전의 경우 모든 요소가 미리 있습니다. 온라인 알고리즘의 문제는 큰 요소를 패킹하는 것이 어렵다는 것입니다. 특히 시퀀스에서 늦게 발생하는 경우에 그렇습니다. 입력 시퀀스를 정렬하고 큰 요소를 먼저 배치하여 이를 극복할 수 있습니다.
첫 번째 맞춤 감소 -
예시
// C++ program to locate number of bins needed implementing First Fit Decreasing algorithm.
#include <bits/stdc++.h>
using namespace std;
/* We copy firstFit() from above */
int firstFit(int weight1[], int m, int C){
// We have to initialize result (Count of bins)
int res = 0;
// We have to create an array to store remaining space in bins there can be maximum n bins
int bin_rem[m];
// We have to place elements one by one
for (int i = 0; i < m; i++) {
// We have to find the first bin that can accommodate weight1[i]
int j;
for (j = 0; j < res; j++) {
if (bin_rem[j] >= weight1[i]) {
bin_rem[j] = bin_rem[j] - weight1[i];
break;
}
}
// If no bin could accommodate weight1[i]
if (j == res) {
bin_rem[res] = C - weight1[i];
res++;
}
}
return res;
}
// We have to returns number of bins required implementing first fit decreasing offline algorithm
int firstFitDec(int weight1[], int m, int C){
// At first we sort all weights in decreasing order
sort(weight1, weight1 + m, std::greater<int>());
// Now we call first fit for sorted items
return firstFit(weight1, m, C);
}
// Driver program
int main(){
int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
int C = 10;
int m = sizeof(weight1) / sizeof(weight1[0]);
cout<< "Number of bins required in First Fit "
<< "Decreasing : " << firstFitDec(weight1, m, C);
return 0;
} 출력
Number of bins required in First Fit Decreasing : 3
첫 번째 맞춤 감소는 요소가 먼저 정렬될 때 샘플 입력에 대해 최상의 결과를 생성합니다.
First Fit Decreasing은 자체 균형 이진 검색 트리를 구현하는 O(m log m) 시간에도 사용할 수 있습니다.