資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的裝箱問題（最小化使用的箱子數量）？
給定 m 個不同重量的元素和每個容量為 C 的箱子，將每個元素分配到一個箱子中，以使實現的箱子總數最小化。假設所有元素的重量都小於箱子的容量。
應用
將資料放置在多個磁碟上。
裝載集裝箱，例如卡車。
在固定長度的廣播/電視臺時段中打包廣告。
作業排程。
示例
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
以下近似演算法已為此問題實現。
線上演算法
這些演算法是為裝箱問題實現的，其中元素一次一個地到達（以未知順序），每個元素必須放入一個箱子中，然後再考慮下一個元素。
下一個擬合 -
處理下一個元素時，驗證它是否適合與最後一個元素相同的箱子。僅當它不適合時，才實現一個新箱子。
以下是此演算法的 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
下一個擬合被視為一個簡單的演算法。它只需要 O(m) 時間和 O(1) 的額外空間來處理 m 個元素。
首次擬合 -
處理下一個元素時，按順序檢查或掃描前面的箱子，並將元素放置在第一個適合的箱子中。如果元素當時不適合任何現有箱子，我們只啟動一個新箱子。
示例
// 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
首次擬合的上述實現消耗 O(m2) 時間，但首次擬合可以在 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
最佳擬合也可以在 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
首次擬合遞減為示例輸入生成最佳結果，因為元素首先被排序。
首次擬合遞減也可以在 O(m log m) 時間內使用自平衡二叉搜尋樹實現。
更新於： 2020年1月29日
3K+ 次檢視
廣告