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
