贪婪算法-----装箱问题

贪婪算法

• 贪婪准则
  • 算法在推进的过程中，每一步都追求最优解
  • 贪婪准则一旦确定，中途不能改变
• 贪婪算法求出的最终解不一定是最优解

装箱问题

• 问题描述：有若干个体积为V的箱子，有n个体积为V0，V1，V2，V3…Vn-1的物品
• 要求：把所有物品都装入箱子中，使打开的箱子尽可能少
• 解决思路

  • 贪婪准则

    • 将所有物品按体积的降序排序
    • 每次取出一个物品（当前未装入物品的体积最大值）
    • 遍历所有已打开的箱子，将物品放入最早打开的箱子

  • 存储形式：链表
    

  • 类型声明
    1.排序物品体积时物品的类型

typedef struct{
	int gno;//物品编号
	int gv;//物品体积
}ElemG;

      2.装箱时物品的类型

typedef struct node{
	int gno;//物品编号
	struct node* link;//指向下一个节点的指针域
}GoodsLink;

      3.箱子节点

typedef struct box{
	int Reminder;//存放箱子剩余体积
	GoodsLink *hg；//指向物品的地址
	struct box* next;//指向下一个箱子的指针域
}EBOX;

• 算法描述
  1.创建物品信息，并初始化

ElemG* Init_Goods(){
	int v[N] = {3,2,5,8,10,1,6,12,19,4}; //物品的体积 
	
	ElemG *g;
	g = (ElemG *)malloc((N)*sizeof(ElemG));//存储物品的数组 
	for(int i=0;i<N;i++){
		//初始化物品 
		g[i].gno = i;
		g[i].gv = v[i];
	}
	return g; 
}

2.把所有物品体积按照降序的顺序排序

//将储存物品的进行降序排序 (使用快排)
void GoodsSort(ElemG *g,int left,int right){
	ElemG temp;
	 
	if(left > right){
		return;
	}else{
		int base = g[left].gv;
		int i = left;
		int j = right;
		while(i != j){
			while(base >= g[j].gv && i<j){
				j--;
			}
			
			while(base <= g[i].gv && i<j){
				i++;
			}
			if(i < j){
				temp = g[i];
				g[i] = g[j];
				g[j] = temp;
			}
		}
		temp = g[left];
		g[left] = g[i];
		g[i] = temp;
		
		GoodsSort(g,left,i-1);
		GoodsSort(g,i+1,right);
	}
}

3.装箱

EBox* Load(ElemG* g){
	//初始化箱子 
	EBox* hBox,*tail;//hBox指向头结点，tail指向尾节点 
	hBox = tail = NULL;
	
	//开始装箱 
	for(int i=0;i<N;i++){
		EBox* p;
		for(p = hBox;p && p->Reminder<g[i].gv;p = p->next);
		
		//定义装箱时物品节点并初始化 
		GoodsLink* gl = (GoodsLink*)malloc(sizeof(GoodsLink)); 
		gl->gno = g[i].gno;
		gl->link = NULL;
		
		if(!p){
			//新建箱子节点并初始化
			p = (EBox*)malloc(sizeof(EBox));
			p->hg = gl;
			p->next = NULL;
			p->Reminder = V-g[i].gv;
			//挂箱子（区分头结点和中间节点） 
			if(!hBox){
				hBox = tail = p;
			}else{
				tail ->next = p;
				tail = p;
			}
		}else{
			//将物品放置到已建立的箱子
			p->Reminder = p->Reminder - g[i].gv;
			GoodsLink* a = p->hg;
			while(a->link != NULL){
				a = a->link;
			}
			a->link = gl;
		}
	}
	return hBox;
}

4.输出

//输出 
void print(EBox* hBox){
	EBox* p = hBox;
	GoodsLink* gl;
	while(p){
		printf("箱子剩下的体积:%d--",p->Reminder);
		printf("---箱子装的物品编号:");
		for(gl = p->hg;gl;gl = gl->link){
			printf("%d,",gl->gno);
		}
		printf("\n");
		
		p = p->next;
	}
}