数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装设计学
法学C++ 程序来实现装箱算法
装箱问题是一种特殊的裁剪问题。在装箱问题中，必须将不同体积的物体装入数量有限的容器或箱子中，每个容器或箱子的体积为 V，并且以最少化使用的容器或箱子的数量的方式装入。在计算复杂性理论中，这是一个组合 NP 难问题。
当容器或箱子的数量限制为 1，并且每个物品都以体积和价值来表征时，最大化可以装入容器或箱子中的物品价值的问题被称为背包问题。
算法
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 << "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
更新日期：2019-07-30
1K+ 浏览
广告