山东大学数据结构课设箱子装箱问题附实验报告

在箱子装载问题中，有若干个容量为c的箱子和n个待装载入箱子中的物品。物品i需占是s[i]个单元（0<s[i]n依次取100，200，500，1000，比较以上四种方法（在时间上和所用箱子的数量上）的性能。 ->FF，FFD方法使用竞赛树结构，BF，BFD使用AVL树结构。

#pragma once
#include “AVLTree.h“
#include “AVLTreeNode.h“
#include “binType.h“
#include 
#include  “completeWinnerTree.h“
#include 
#include 
#include “dBinarySearchTreeWithGE.h“

using namespace std;

void select_sort（int *array int n）
{
	int i j t;
	for （i = 1; i< n; i++）
	{
		for （j = i + 1; j		{
			if （array[j] > array[i]）
			{
				t = array[j];
				array[j] = array[i];
				array[i] = t;
			}
		}
	}



}

void firstFitPack（int *objectSize int numberOfobjects int binCapacity）
{//输出箱子容量为binCapacity的最先适配装载
 //objectSize[1:numberOfobjects]是物品大小
 //初始化一个放箱子编号的数组
	int n = numberOfobjects;
	int *number = new int[n + 1];

	//初始化n个箱子和赢者树
	binType *bin = new binType[n + 1];      //箱子
	for （int i = 1; i <= n; i++）
		bin[i].unusedCapacity = binCapacity; //箱子的剩余容量
	completeWinnerTree winTree（bin n）;

	//将物品装到箱子里
	for （int i = 1; i <= n; i++）
	{//把物品i装入一个箱子
	 //找到第一个有足够容量的箱子
		int child = 2;  //从根的左孩子开始搜索
		while （child < n）
		{
			int winner = winTree.winner（child）;
			if （bin[winner].unusedCapacity < objectSize[i]）
				child++;      //第一个箱子在右子树
			child *= 2;       //移动到左孩子
		}

		int binToUse;     //设置为要使用的箱子
		child /= 2;     //撤销向最后的左孩子的移动
		if （child < n）
		{//在一个树节点
			binToUse = winTree.winner（child）;
			//若binToUse是右孩子，则要检查箱子binToUse-1
			//即使binToUse是左孩子，检查箱子binToUse-1也不会有问题
			if （binToUse > 1 && bin[binToUse - 1].unusedCapacity >= objectSize[i]）
				binToUse--;
		}
		else  //当n是奇数
			binToUse = winTree.winner（child / 2）;
		number[i] = binToUse;

	//	cout << “物品“ << i << “装到第“ << binToUse<<“个箱子中“ << endl;
		bin[binToUse].unusedCapacity -= objectSize[i];
		winTree.rePlay（binToUse）;

	}
	select_sort（number n）;
	cout << “使用的箱子数：“ << number[1] << endl;
}

void bestFitPack（int *objectSize int numberOfobjects int binCapacity）
{//输出容量为binCapacity的最优箱子匹配.
 //objectSize[1:numberOfobjects]是物品大小
	int n = numberOfobjects;
	int *number = new int[n + 1];
	int binsUsed = 0;
	AVLTree*theTree = new AVLTree（）;
	AVLTreeNode*theBin=new AVLTreeNode（）;
	
	
	//将物品逐个装箱
	for （int i = 1; i <= n; i++）
	{//将物品i装箱
	 //寻找最匹配的箱子

		
		AVLTreeNode *bestBin = theTree->findGE（objectSize[i]）;
		
		if （bestBin == NULL）
		{//没有足够大的箱子，启用一个新箱子
			theBin->key = binCapacity;
			theBin->n = ++binsUsed;
			
		}
		else
		{
			//从树theTree中删除最匹配的箱子
			*theBin = *bestBin;
       theTree->remove（bestBin->key）;
		}
		number[i] = theBin->n;
	//	cout << “物品“ << i << “装到第“ << theBin->n << “个箱子中“<< endl;
		//将箱子插到树中，除非箱子已满
		theBin->key = theBin->key - objectSize[i];
	//	cout << “箱子“ << theBin->n << “剩“ << theBin->key << “空间“ << endl;
		if （theBin->key > 0）
			theTree->insert（theBin->keytheBin->n）;
		//theTree->print（）;
		//cout << endl;
		//cout << endl;
		//cout << endl;
	}

	select_sort（number n）;
	cout << “所用箱子数:“ << number[1] << endl;

}
/*void best（int *objectSize int numberOfOb

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     159892  2018-04-12 11:09  箱子装箱问题\箱子装箱问题.docx

     文件      12134  2017-05-20 15:54  箱子装箱问题\代码\AVLTree.h

     文件        559  2017-05-20 13:48  箱子装箱问题\代码\AVLTreeNode.h

     文件        595  2017-05-09 14:36  箱子装箱问题\代码\binaryTreeNode.h

     文件        180  2017-05-02 12:49  箱子装箱问题\代码\binType.h

     文件       3392  2017-05-02 15:29  箱子装箱问题\代码\completeWinnerTree.h

     文件       7403  2017-05-13 12:36  箱子装箱问题\代码\ConsoleApplication2.vcxproj

     文件       1645  2017-05-13 12:36  箱子装箱问题\代码\ConsoleApplication2.vcxproj.filters

     文件       3653  2017-05-13 10:25  箱子装箱问题\代码\dBinarySearchTreeWithGE.h

     文件       2643  2017-05-02 15:29  箱子装箱问题\代码\myExceptions.h

     文件       6105  2017-05-20 15:57  箱子装箱问题\代码\packing.cpp

     文件       2533  2017-05-02 15:20  箱子装箱问题\代码\packing.h

     文件        362  2017-05-08 20:59  箱子装箱问题\代码\pair.h

     文件        304  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleApplication2.log

     文件     232607  2017-05-20 15:57  箱子装箱问题\代码\Debug\packing.obj

     文件     879616  2017-05-20 15:57  箱子装箱问题\代码\Debug\vc141.idb

     文件     569344  2017-05-20 15:57  箱子装箱问题\代码\Debug\vc141.pdb

     文件        890  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleA.C0DA3C2C.tlog\CL.command.1.tlog

     文件      41886  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleA.C0DA3C2C.tlog\CL.read.1.tlog

     文件        872  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleA.C0DA3C2C.tlog\CL.write.1.tlog

     文件        247  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleA.C0DA3C2C.tlog\ConsoleApplication2.lastbuildstate

     文件       1560  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleA.C0DA3C2C.tlog\link.command.1.tlog

     文件       3462  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleA.C0DA3C2C.tlog\link.read.1.tlog

     文件        844  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleA.C0DA3C2C.tlog\link.write.1.tlog

     目录          0  2017-05-20 15:57  箱子装箱问题\代码\Debug\ConsoleA.C0DA3C2C.tlog

     目录          0  2017-05-20 15:57  箱子装箱问题\代码\Debug

     目录          0  2018-04-12 11:12  箱子装箱问题\代码

     目录          0  2017-05-20 15:57  箱子装箱问题

----------- ---------  ---------- -----  ----

              1932728                    28

............此处省略1个文件信息