实现装箱算法的 C++ 程序

• Z时代
• 2024-01-10
• 分类：综合

装箱问题是一种特殊类型的下料问题。在装箱问题中，不同体积的物体必须以最小化所用箱数的方式装入有限数量的容器或箱中，每个容器或箱的每个体积为 V。在计算复杂性理论中，它是一个组合的 NP-hard 问题。

当 bin 的数量限制为 1 并且每个物品都以体积和价值为特征时，最大化可以放入 bin 的物品的价值的问题称为背包问题。

算法

Begin
   Binpacking(pointer, size, no of sets)
   Declare bincount, m, i
   Initialize bincount = 1, m=size
   For i = 0 to number of sets
   if (m - *(a + i) > 0) do
      m = m - *(a + i)
      Continue
   Else
      Increase bincount
      m = size;
      Decrement i
      Print number of bins required
End

示例代码

#include<iostream>
using namespace std;
void binPacking(int *a, int size, int n) {
   int binCount = 1;
   int m = size;
   for (int i = 0; i < n; i++) {
      if (m - *(a + i) > 0) {
         m -= *(a + i);
         continue;
      } else {
         binCount++;
         m = size;
         i--;
      }
   }
   cout << "所需的垃圾箱数量： " << binCount;
}
int main(int argc, char **argv) {
   cout << "输入 Set 中的项目数： ";
   int n;
   cin >> n;
   cout << "Enter " << n << " items:";
   int a[n];
   for (int i = 0; i < n; i++)
      cin >> a[i];
   cout << "输入箱大小： ";
   int size;
   cin >> size;
   binPacking(a, size, n);
}

输入 Set 中的项目数： 3
Enter 3 items:4
6
7
输入箱大小： 26
所需的垃圾箱数量： 1

以上是 实现装箱算法的 C++ 程序 的全部内容， 来源链接： utcz.com/z/352701.html