貪婪算法-----裝箱問題

貪婪算法

• 貪婪準則
  • 算法在推進的過程中，每一步都追求最優解
  • 貪婪準則一旦确定，中途不能改變
• 貪婪算法求出的最終解不一定是最優解

裝箱問題

• 問題描述：有若幹個體積為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;
	}
}