数据结构
网络
关系数据库管理系统
操作系统
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+ 次查看
广告