Trong trường hợp có m phần tử có trọng lượng khác nhau và mỗi thùng có dung tích C, hãy gán mỗi phần tử vào một thùng sao cho tổng số thùng thực hiện là nhỏ nhất. Giả định rằng tất cả các phần tử có trọng lượng nhỏ hơn dung lượng thùng.
Ứng dụng
-
Đặt dữ liệu trên nhiều đĩa.
-
Xếp các thùng chứa như xe tải.
-
Đóng gói quảng cáo trong thời lượng cố định của đài phát thanh / đài truyền hình.
-
Lập kế hoạch công việc.
Ví dụ
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} Giới hạn dưới
Chúng ta luôn có thể tính toán giới hạn dưới về số thùng tối thiểu được yêu cầu bằng cách sử dụng hàm ceil (). Giới hạn dưới có thể được đưa ra bên dưới -
-
Các thùng có số lượng tối thiểu> =ceil ((Tổng trọng lượng) / (Dung tích thùng))
-
Trong ví dụ trên, giới hạn dưới cho ví dụ đầu tiên là “ceil (4 + 1 + 8 + 2 + 4 + 1) / 10” =2
-
Các thuật toán gần đúng sau được triển khai cho vấn đề này.
Thuật toán trực tuyến
Các thuật toán này được triển khai cho các vấn đề Đóng gói thùng trong đó các phần tử đến lần lượt (theo thứ tự không xác định), mỗi phần tử phải được đặt trong một thùng, trước khi xem xét phần tử tiếp theo.
Phù hợp tiếp theo -
Khi xử lý phần tử tiếp theo, hãy xác minh xem phần tử đó có nằm trong cùng một thùng với phần tử cuối cùng hay không. Chỉ triển khai một thùng mới nếu không.
Sau đây là ứng dụng C ++ cho thuật toán này.
// 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;
} Đầu ra
Number of bins required in Next Fit : 4
Next Fit được coi như một thuật toán đơn giản. Nó chỉ cần O (m) thời gian và thêm O (1) không gian để xử lý m phần tử.
Đầu tiên Fit−
Khi xử lý phần tử tiếp theo, hãy kiểm tra hoặc quét các thùng trước đó theo thứ tự và đặt phần tử đó vào thùng đầu tiên phù hợp.
Ví dụ
// 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;
} Đầu ra
Number of bins required in First Fit : 4
Việc triển khai First Fit ở trên tiêu tốn O (m2) thời gian, nhưng First Fit có thể được sử dụng trong O (m log m) thời gian triển khai Cây tìm kiếm nhị phân tự cân bằng.
Phù hợp nhất -
Khái niệm là đặt mục tiếp theo ở vị trí chặt chẽ nhất. Điều đó có nghĩa là hãy đặt nó vào thùng để ít nhất còn lại khoảng trống.
Ví dụ
// 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;
} Đầu ra
Number of bins required in Best Fit : 4
Best Fit cũng có thể được áp dụng trong khoảng thời gian O (m log m) triển khai Cây tìm kiếm nhị phân tự cân bằng.
Thuật toán ngoại tuyến
Trong trường hợp của phiên bản ngoại tuyến, chúng tôi đã trả trước tất cả các phần tử. Chúng ta có thể khắc phục điều này bằng cách sắp xếp trình tự đầu vào và đặt các phần tử lớn trước.
Giảm phù hợp đầu tiên -
Ví dụ
// 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;
} Đầu ra
Number of bins required in First Fit Decreasing : 3
Việc giảm First Fit tạo ra kết quả tốt nhất cho đầu vào mẫu vì các phần tử được sắp xếp trước.
Giảm phù hợp đầu tiên cũng có thể được sử dụng trong thời gian O (m log m) triển khai Cây tìm kiếm nhị phân tự cân bằng.