实现装箱算法的 C++ 程序
装箱问题是一种特殊类型的下料问题。在装箱问题中，不同体积的物体必须以最小化所用箱数的方式装入有限数量的容器或箱中，每个容器或箱的每个体积为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输出结果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