欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贪婪算法之装箱问题

程序员文章站 2022-06-04 10:49:29
...

贪婪算法:简单高效

 

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;
}
贪婪算法之装箱问题