C++ 程序实现装箱算法

c++server side programmingprogramming

装箱问题是一种特殊类型的裁切库存问题。在装箱问题中,必须将不同体积的物体装入有限数量的容器或箱子中,每个容器或箱子的体积为 V,以使使用的箱子数量最少。在计算复杂性理论中,这是一个组合 NP 难问题。

当箱子数量限制为 1 且每件物品都具有体积和价值时,最大化可装入箱子的物品价值的问题称为背包问题。

算法

开始
   Binpacking(pointer, size, no of sets)
   声明 bincount, m, i
   初始化 bincount = 1, m=size
   对于 i = 0 到集合数
   如果 (m - *(a + i) > 0) 执行
      m = m - *(a + i)
      继续
   否则
      增加 bincount
      m = size;
      减少 i
      打印所需的 bin 数
结束

示例代码

#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 << "Number of bins required: " << binCount;
}
int main(int argc, char **argv) {
   cout << "Enter the number of items in Set: ";
   int n;
   cin >> n;
   cout << "Enter " << n << " items:";
   int a[n];
   for (int i = 0; i < n; i++)
      cin >> a[i];
   cout << "Enter the bin size: ";
   int size;
   cin >> size;
   binPacking(a, size, n);
}

输出

Enter the number of items in Set: 3
Enter 3 items:4
6
7
Enter the bin size: 26
Number of bins required: 1

相关文章