贪婪算法之装箱问题

贪婪算法：简单高效

 

1. 贪婪准则：

(1) 算法在推进的过程中，每一步都要得到最优解，（追求局部最优）

(2) 贪心准则一旦设置好，不再改变

2. 贪婪准则不一定可

3. 以获得最优解

 

装箱问题

 

1. 问题描述：

(1) 有若干个体积为v的箱子

(2) 若n个物品体积为：v0,V1,V2,V3.....Vn-1

要求：将所有物品都装入箱子中，使打开的箱子尽可能少

2. 贪心准则

(1) 将所有物品按体积降序排列

(2) 每次取出一个物品，该物品为当前没有装入箱子的物品中体积最大的

(3) 遍历所有已经打开的箱子，将该物品放入较早打开的箱子，若已打开的箱子都放不下了则打开一个新箱子

1. 存储：链表

(1) 一条链为箱子链，每个箱子中有一个物品链

2. 类型声明

(1) 物品信息：

typedef struct{

int gno; //物品编号

int gv; //物品体积

} ElemG ;

 

物品集和，假设有n个物品

 

gno

gv

 

(2) 物品结点

     typedef struct node{

int gno; //物品编号

struct node* link; //箱子中的物品结点的next指针

} goodslink;

 

(3) 箱子结点

typedef struct box{

int remainder; //剩余体积

GoodsLink * hg; //物品链头指针

GoodsLink * tail; //物品链的尾指针

struct box* next; // 指针域

}BoxLink;

 

3. 算法描述

(1) 创建物品信息数组，并初始化

(2) 把所有的物品按体积降序排列

(3) 装箱

① 遍历所有已经排好序的物品

1. 遍历箱子链；

2. 如果p为空（遍历完一遍后，新物品放不进已有的所有箱子），开新箱子：创建箱子结点给p，初始化箱子，挂箱子（首先判断箱子链是否为空）

3. 放物品

(1) 更新新箱子的剩余体积

(2) 创建物品结点

(3) 判断是否为新箱子，若是新箱子直接放物品链头节点，否则放物品链尾节点

(4) 输出

代码实现及输出结果如下

#include<stdio.h> 
#include<stdlib.h>
#include<time.h>
#define V 50 
//物品信息 
typedef struct{
	int gno;	//物品编号
	int gv; 	//物品体积 
} ElemG ; 

//物品结点 
typedef struct node{
	int gno;	//物品编号 
	struct node* next;	//箱子中的物品结点的next指针 
} GoodsLink;

//箱子结点
typedef struct box{
	int remainder;		//剩余体积
	GoodsLink * ghead;	//物品链头指针 
	GoodsLink * gtail;	//物品链的尾指针 
	struct box* next;	// 指针域 
}BoxLink;

//排序 
void Sort (ElemG *g, int num){
	ElemG temp;
	int i,j;
	//冒泡排序 
	for (i = 0; i < num-1; i++){
		for(j = 1; j < num-i; j++){
			if(g[j-1].gv < g[j].gv){
				temp = g[j-1];	//相同结构体类型变量间可直接交换赋值 
				g[j-1] = g[j];
				g[j] = temp;
			}	
		}
	}
	printf("物品所占体积从大到小的顺序为：\n");	
	for(int i = 0; i < num; i++){
		printf("%2d：编号 %2d, 体积 %2d\n", i+1, g[i].gno, g[i].gv);
	}
}

//物品装箱
BoxLink* Packing(ElemG *goods, int num){
	BoxLink* p ,* hbox = NULL, *tail = NULL;	//p用来遍历， hbox箱子链头节点,tail箱子尾节点 
	GoodsLink* g = NULL; 	//物品结点指针 
	printf("执行装箱。\n");	
	for (int i = 0; i <num; i++){	//将所有的物品装完为止
		//找合适的箱子将物品放下，
		for(p = hbox; p&&p->remainder < goods[i].gv; p = p->next);
		//当p == NULL时， 表示还没箱子或者所有箱子都放不下当前物品时需要建新箱子 
		if(p == NULL){
			p = (BoxLink*)malloc(sizeof(BoxLink)) ;
			p->remainder = V;
			p->ghead = p->gtail = NULL; 	
			p->next = NULL;
			if(hbox == NULL){		//没有箱子 
				hbox = tail = p; 
			}else{	//已经有了箱子链，自需要将新箱子挂再链尾 
				tail = tail->next = p;
			}
		}
		//找到了合适的箱子，则进行装箱 
		p->remainder -= goods[i].gv;
		//创建物品链结点 
		g = (GoodsLink*)malloc(sizeof(GoodsLink));
		g->next = NULL;
		g->gno = goods[i].gno;
		if (p->ghead == NULL){	//如果是新箱子，将物品链的头尾指针都指向该结点 
			p->ghead = p->gtail = g; 
		} 
		else{
			p->gtail = p->gtail->next = g;
		}
									 							
	} 							
	return hbox;
}

//输出
void PrintGoods(BoxLink* hbox, ElemG* goods){
	BoxLink* b = hbox;
	GoodsLink* g = NULL; 
	printf("将装入箱子的物品按序输出：\n");
	int i = 1; 
	while(b){			//时间复杂度 O(n^3) 
		printf("第%d个箱子中的物品(编号：体积)：", i++);
		g = b->ghead;
		int no = 0;		//物品编号 
		while(g){
			//每次输出物品信息前，先找该物品在排序后的物品数组中的位置（下标） 
			//遍历物品数组，当箱子中物品链中的物品的编号和物品数组中的物品编号相同时，
			//此时的 no 即为该物品在物品数组中的下标 
			while(g->gno != goods[no].gno)	
				no++; 
			printf("%2d:%2d, ",g->gno, goods[no].gv );
			g = g->next;
		}
		printf("\n");
		b = b->next; 
	}
} 

int main(void){
	ElemG* goods;	//物品信息结构体数组
	GoodsLink* glink;	//物品链头节点 
	int num;		//物品数量
	printf("请输入物品的个数：");
	scanf("%d",&num); 
	if(num < 1){
		printf("没有物品，不需要装箱。\n");
		return 0;
	}
	goods = (ElemG*)malloc(num * sizeof(ElemG));
	srand((int) time(NULL));
	//初始化
	for(int i = 1; i <= num; i++){
		goods[i-1].gno = i;
		goods[i-1].gv = rand()%30 +1;	//产生从1 到 30 的随机数（共30个数） 			
//		scanf("%d",&goods[i-1].gv);
//		fflush(stdin);
	} 
	printf("物品信息：\n");	
	for(int i = 0; i < num; i++){
		printf("编号 %2d：体积 %2d\n", goods[i].gno, goods[i].gv);
	}
	//将物品按体积降序排列
	Sort(goods, num); 
	BoxLink* root;	//生成箱子链的头节点
	root = Packing(goods, num);
	PrintGoods(root, goods);
	return 0;
}