matlab 大数据平台 PaddleHub less jquery dataframe csv security flash coldfusion grid Pure CSS php项目实战 mysql当前时间减一天 mysql安装后怎么使用 matlab求矩阵最大值 oracle查询数据库 plsql连接mysql hadoop环境变量配置 python正则 python练习 python教学 python打开文件 javalabel java实例 java基础语言 java使用mysql java初级教程 java在线课程 java定义接口 java基础框架 java命令 java中string的方法 java中random 图片链接生成器 eml文件阅读器下载 生存猎人属性 微信小程序源代码 c语言图书管理系统 android应用开发入门
当前位置: 首页 > 学习教程  > 编程语言

箱子最优化匹配,数据结构(c++)

2021/2/13 18:09:04 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目描述:某一运输公司要将n个物品装到m个箱子中,每个物品都有一定的重量,每个箱子都有容量限制,如何用最少的箱子装载物品? 说明:每个箱子的容量为M,物品i需要占用的箱子容量为W[i]&#xff0c…

题目描述:某一运输公司要将n个物品装到m个箱子中,每个物品都有一定的重量,每个箱子都有容量限制,如何用最少的箱子装载物品?
说明:每个箱子的容量为M,物品i需要占用的箱子容量为W[i],0<=W[i]<=M。
最优匹配法:令箱子j的可用用量为b[j],物品i应放入可用容量最小但不小于w[i]的箱子里。采用二叉查找树实现最优匹配法。
功能要求及说明:
(1)给定给各箱子的剩余容量,根据剩余容量大小,构造二叉查找树;
(2)给定各物品的重量wi,根据要装入的物品需要占用的箱子容量w[i],在二叉查找树中查询最适合它的箱子,修改该箱子的剩余容量;
(3)从二叉查找树中删除被选中的箱子;
(4)将减少了容量的箱子再插入到二叉查找树中;
(5)打印最终的装箱结果;
(6)采用模块化设计,分别以函数形式描述上述各功能。

class BSTNode {
private:
   	int key; //箱子容量
	int value;//箱子编号
	BSTNode* ln;//箱子编号
	BSTNode* rn;
public:
    //无参构造函数
	BSTNode() {
		ln = rn = NULL;
	}
	//有参构造函数
	BSTNode(int key, int a, BSTNode* ln = NULL, BSTNode* rn = NULL) :key(key), value(a), ln(ln), rn(rn) {}
	inline int getValue();//获取箱子容量
	inline void setValue(int value) ;//设置箱子容量
	inline int getKey();//获取箱子编号
	inline void setKey(int key);//设置箱子编号
inline BSTNode* left();//返回左孩子指针
	inline void setLeft(BSTNode* ln) ;//设置左孩子指针
	inline BSTNode* right() ;//返回右孩子指针
	inline void setRight(BSTNode* rn) ;//设置右孩子指针
};
class BST {
private:
	BSTNode* inserthelp(BSTNode*, int&, int&);//插入节点核心函数
	BSTNode* removehelp(BSTNode*, int&);//删除节点核心函数
	void printhelp(BSTNode* root);//输出二叉树核心函数
	BSTNode* getmin(BSTNode*);//获取最小节点
	BSTNode* deletemin(BSTNode*);//删除最小节点
	BSTNode* findhelp(BSTNode*, int&);//检索节点
	void clearhelp(BSTNode*);//清空二叉树
public:
    BSTNode* root;//二叉树根节点
	int m;//箱子数量
	int *a = new int[MAX];//最优匹配化后的各箱子容量
	BST() {root = NULL;}//无参构造
	BST(int m){//有参构造
	    root = NULL;
	    this->m = m;
	}
	~BST() {clearhelp(root);}	//析构函数
	void insert(int key, int value);//插入接口函数
	void remove(int key) ;//删除接口函数
	BSTNode findGE(int key) ;//查找最合适的箱子
	void findMin(int* a, int n) ;//最优化分配
	void print()//输出二叉树
	int numUserB(int A[]);//输出所有被使用的箱子编号以及数量
};
2、主要算法思想
检索二叉树的建立:根据二叉树的特点,左孩子小于右孩子,在插入发的过程中将检索二叉树建立。
箱子最优匹配法:插入物品的时候优先插入可用空间容量最小且大于物品尺寸的箱子。
由于箱子的剩余容量可能相同,所以我们采用一颗带有重复关键字的二叉搜索树来描述箱子。
节点的键为箱子剩余空间的大小,假如我们要插入物体的尺寸大小为n,我们首先比较该n与根节点的键大小,如果n小于根节点大侠则将n设为候选箱子,然后再根节点的左子树里面继续进行寻找,如果n大于左子树根节点的键,那么就得在左子树根节点的右子树进行寻找,然后重复刚才的查找方法,然后最后一个候选箱子就是我们要插入的那个箱子,然后我们更改箱子的剩余空间,删除这个箱子,然后重新将该箱子插入树中为下一次查找做准备。
四  详细设计
#include <iostream>
#include <string>
using namespace std;
#define MAX  999
//二叉树节点
class BSTNode {
private:
    //箱子容量
	int key;
	//箱子编号
	int value;
	//左右孩子
	BSTNode* ln;
	BSTNode* rn;
public:
    //无参构造函数
	BSTNode() {
		ln = rn = NULL;
	}
	//有参构造函数
	BSTNode(int key, int a, BSTNode* ln = NULL, BSTNode* rn = NULL) :key(key), value(a), ln(ln), rn(rn) {
	}
	~BSTNode() {
	}
	//获取箱子容量
	inline int getValue() {
		return this->value;
	}
	//设置箱子容量
	inline void setValue(int value) {
		this->value = value;
	}
	//获取箱子编号
	inline int getKey() {
		return key;
	}
	//设置箱子编号
	inline void setKey(int key) {
		this->key = key;
	}
	//返回左孩子指针
	inline BSTNode* left() {
		return ln;
	}
	//设置左孩子指针
	inline void setLeft(BSTNode* ln) {
		this->ln = ln;
	}
	//返回右孩子指针
	inline BSTNode* right() {
		return rn;
	}
	//设置右孩子指针
	inline void setRight(BSTNode* rn) {
		this->rn = rn;
	}
};
 
//检索二叉树
class BST {
private:
    //插入节点核心函数
	BSTNode* inserthelp(BSTNode*, int&, int&);
	//删除节点核心函数
	BSTNode* removehelp(BSTNode*, int&);
	//输出二叉树核心函数
	void printhelp(BSTNode* root);
	//获取最小节点
	BSTNode* getmin(BSTNode*);
	//删除最小节点
	BSTNode* deletemin(BSTNode*);
	//检索节点
	BSTNode* findhelp(BSTNode*, int&);
	//清空二叉树
	void clearhelp(BSTNode*);
public:
    //二叉树根节点
	BSTNode* root;
	//箱子数量
	int m;
	//最优匹配化后的各箱子容量
	int *a = new int[MAX];
	//无参构造
	BST() {
		root = NULL;
	}
	//有参构造
	BST(int m){
	    root = NULL;
	    this->m = m;
	}
	//析构函数
	~BST() {
		clearhelp(root);
	}
	//插入接口函数
	void insert(int key, int value) {
		root = inserthelp(root, key, value);
	}
	//删除接口函数
	void remove(int key) {
			removehelp(root, key);
	}
	//查找最合适的箱子
	BSTNode findGE(int key) {
		BSTNode* node = root;
		BSTNode a;
		while (node != NULL) {
			if (node->getKey() >= key) {
				a = *node;
				node = node->left();
			}
			else
				node = node->right();
		}
		return a;
	}
	//最优化分配
	void findMin(int* a, int n) {
		BSTNode B;
		for (int i = 0; i < n; i++) {
			B = findGE(a[i]);
			//删除查找到的合适箱子
			remove(B.getKey());
			//插入修改后的箱子
			insert(B.getKey()-a[i], B.getValue());
		}
	}
	//输出二叉树
	void print() {
        cout<<"编号 "<<" 容量"<<endl;
		if (root != NULL)
			printhelp(root);
	}
	//输出所有被使用的箱子编号以及数量
    int numUserB(int A[]){
        cout<<"使用的分别是一下编号的箱子"<<endl;
        int number = 0;
        for(int i = 0;i<m;i++){
            if(A[i] != a[i]){
                cout<<i<<" ";
                number++;
            }
        }
        cout<<endl;
        return number;
    }
};
//打印二叉树核心函数
void BST::printhelp(BSTNode* root) {
	if (root == NULL) return;
	printhelp(root->left());
	a[root->getValue()] = root->getKey();
	cout << root->getValue()<<"   "<<root->getKey() << endl;
	printhelp(root->right());
}
//获取最小结点
BSTNode* BST::getmin(BSTNode* root) {
	if (root->left() == NULL) return root; else return getmin(root->left());
}
//删除最小结点
BSTNode* BST::deletemin(BSTNode* root) {
	if (root->left() == NULL) return root->right(); else root->setLeft(deletemin(root->left()));
	return root;
}
//删除指定结点
BSTNode* BST::removehelp(BSTNode* root, int& key) {
	if (root == NULL) return NULL;
	else if (key < root->getKey())
		root->setLeft(removehelp(root->left(), key));
    else if (key > root->getKey())
		root->setRight(removehelp(root->right(), key));
    else {
		BSTNode* temp = root;
		if (root->left() == NULL) {
			root = root->right();
			delete temp;
		}
		else if (root->right() == NULL) {
			root = root->left();
			delete temp;
		}
		else {
			BSTNode* t = getmin(root->right());
			root->setValue(t->getValue());
			root->setKey(t->getKey());
			root->setRight(deletemin(root->right()));
			delete t;
		}
	}
	return root;
}
//插入核心函数
BSTNode* BST::inserthelp(BSTNode* root, int& key, int &value) {
	if (root == NULL) return new BSTNode(key, value);
	if (key < root->getKey()) root->setLeft(inserthelp(root->left(), key, value));
	else root->setRight(inserthelp(root->right(), key, value));
	return root;
}
//清空二叉树
void BST::clearhelp(BSTNode* root) {
	if (root == NULL) return;
	clearhelp(root->left());
	clearhelp(root->right());
	delete root;
}
//主函数
int main() {
    //箱子数
	int m;
	cout << "输入箱子个数m=";
	cin >> m;
	//箱子数组
	int b[MAX];
	BST r(m);
	cout << "输入每个箱子的容量" << endl;
	for (int i = 0; i < m; i++) {
		cin >> b[i];
		r.insert(b[i], i);
	}
	//物品数
	int n;
	cout << "请输入物品个数n=";
	cin >> n;
	//物品数组
	int w[MAX];
	cout << "请输入每一个物品的重量" << endl;
	for (int i = 0; i < n; i++)
		cin >> w[i];
    cout<<"建造的搜索二叉树是"<<endl;
	r.print();
	r.findMin(w, n);
	cout<<"经过最优化分配后的搜索二叉树是"<<endl;
	r.print();
	int number = r.numUserB(b);
	cout<<"使用的箱子的数量是"<<number<<endl;
}

此处是报告链接


本文链接: http://www.dtmao.cc/news_show_700191.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?