一、问题描述

①在箱子装载问题中，有若干个容量为c的箱子和n个待装载入箱子中的物品。物品i需占是s[i]个单元（0<s[i]<=c）。所谓成功装载（feasible packing），是指能把所有物品都装入箱子而不溢出，而最优装载（optimal packing）是指使用了最少箱子的成功装载。对于箱子装载问题，有4种流行的求解算法。

②基本要求：

->n依次取100，200，500，1000，比较以上四种方法（在时间上和所用箱子的数量上）的性能。

->FF，FFD方法使用竞赛树结构，BF，BFD使用二叉搜索树结构。

二、需求描述

1.4种流行的求解算法：

<1>最先匹配法（FF）：物品按1,2...,n的顺序装入箱子。假设箱子从左至右排列，每一物品i放入可盛载它的最左箱子。

<2>最先匹配递减法（FFD）：方法与FF类似，区别在于各物品首先按容量递减的次序排列，即对于1<=i<n,有s[i]>=s[i+1].

<3>最优匹配法（BF）：设c[j]为箱子j的可用容量，初始时，所有箱子的可负载容量为c。物品i放入具有最小c且容量大于s[i]的箱子中。

<4>最优匹配递减法（BFD）：方法与BF相似，区别在于各物品首先按容量递减的次序排列，即对于1<=i<n,有s[i]>=s[i+1].

2.输入要求：

①第一种输入方式：n在程序中固定读入100,200,500,1000个数，这些数预先在文本中手动输入为固定的无序正整数。

②第二种输入方式：n为程序运行后，人为输入的数n，并且生成n个随机数，用作程序所需要测试的物品大小数。

3.输出要求：

输出的要求为：直观的分析排列出在不同的箱子数量、不同的物品数量以及不同的物品大小的情况下，上述四种方法在时间上和所用的箱子的数量上的不同。

比较四种方法的性能。

4.界面设计：

使用的是程序运行控制台输出，没有使用图形化界面。

界面设计如图：

①第一种输入方式：

②第二种输入方式

5.测试设计：

使用第一种方式输入数据：首先分别将100,200,500,1000个数据输入到一个文本文件中，然后在程序中使用读取文件的方法将文本文件的数据当做程序的测试数据，进行测试实验。

读取文件的方法为：

使用的测试数据为：

①100个数据

②200个数据

③500个数据

④1000个数据

数据就是大同小异啦，自己建立txt文件输入数据就好

三、设计

待续...

整理大二时写的数据结构课设代码，之中还有很多问题，待修改后再放上来。

整理于2017年4月26日

【数据结构】--C++实现箱子装箱问题