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（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;
//我们必须返回实现下一个适合在线算法所需的垃圾箱数量
int nextFit(int weight1[], int m, int C){
   //结果（仓数）和当前仓中的剩余容量被初始化。
   int res = 0, bin_rem = C;
   //我们必须一一放置元素
   for (int i = 0; i < m; i++) {
      //如果此元素无法放入当前bin中
      if (weight1[i] > bin_rem) {
         res++; // Use a new bin
         bin_rem = C - weight1[i];
      }
      else
      bin_rem -= weight1[i];
      }
   return res;
}
//驱动程序
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被视为一种简单算法。它只需要O(m)时间和O(1)额外空间即可处理m个元素。

第一次适合-

在处理下一个元素时，请按顺序检查或扫描先前的容器，然后将其放入适合的第一个容器中。如果该元素当时不适合任何现有容器，则我们仅启动一个新容器。

示例

// C++ program to find number of bins needed implementing First Fit algorithm.
#include <bits/stdc++.h>
using namespace std;
//我们必须返回实现首次拟合在线算法所需的垃圾箱数量
int firstFit(int weight1[], int m, int C){
   //我们必须初始化结果（箱数）
   int res = 0;
   //我们必须创建一个数组以将剩余空间存储在垃圾箱中，最多可以有n个垃圾箱
   int bin_rem[m];
   //我们必须一一放置元素
   for (int i = 0; i < m; i++) {
      //箱
      int j;
      for (j = 0; j < res; j++) {
         if (bin_rem[j] >= weight1[i]) {
            bin_rem[j] = bin_rem[j] - weight1[i];
            break;
         }
      }
      //如果没有箱可容纳重量1 [i]
      if (j == res) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   }
   return res;
}
//驱动程序
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可以在O（m log m）的时间内实现自平衡二叉搜索树。

最适合-

概念是将下一个项目放在最紧的位置。这意味着将其放入垃圾箱，以便至少留出空白空间。

示例

// C++ program to calculate number of bins required implementing Best fit algorithm.
#include <bits/stdc++.h>
using namespace std;
//我们必须返回实现最佳拟合在线算法所需的垃圾箱数量
int bestFit(int weight1[], int m, int C){
   //我们必须初始化结果（箱数）
   int res = 0;
   //我们必须创建一个数组以将剩余空间存储在垃圾箱中，最多可以有n个垃圾箱
   int bin_rem[m];
   //逐一放置元素
   for (int i = 0; i < m; i++){
      //的最佳垃圾箱
      int j;
      //我们必须初始化剩余的最小空间和最佳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];
      }
   }
   //如果没有一个箱可以容纳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;
}
//驱动程序
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){
   //我们必须初始化结果（箱数）
   int res = 0;
   //我们必须创建一个数组以将剩余空间存储在垃圾箱中，最多可以有n个垃圾箱
   int bin_rem[m];
   //我们必须一一放置元素
   for (int i = 0; i < m; i++) {
      //箱
      int j;
      for (j = 0; j < res; j++) {
         if (bin_rem[j] >= weight1[i]) {
         bin_rem[j] = bin_rem[j] - weight1[i];
         break;
      }
   }
   //如果没有箱可容纳重量1 [i]
      if (j == res) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   }
return res;
}
//我们必须返回实现首次拟合递减离线算法所需的垃圾箱数量
int firstFitDec(int weight1[], int m, int C){
   //首先，我们按降序对所有权重进行排序
   sort(weight1, weight1 + m, std::greater<int>());
   //现在，我们称“最适合已排序项目”
   return firstFit(weight1, m, C);
}
//驱动程序
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）时间中使用，以实现自平衡二进制搜索树。