贪心算法（装箱问题）

贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。因此能够使用贪心算法的问题必须满足下面的两个性质：

1.整体的最优解可以通过局部的最优解来求出；

2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。

3.局部最优解不一定能得到整体最优解。

 

贪心算法之装箱问题：

有若干个体积为V的箱子，有n个物品体积为v1，v2，v3，v4。。。。

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

算法描述：把所有物品按体积降序排序，每次取出一个物品（该物品为当前体积最大的物品），遍历所有已打开箱子，将该箱子放入一个较早打开的箱子，若没有箱子能放下，则打开一个新箱子。

 

完整代码实现：

#include<stdio.h>
#include<stdlib.h>
#define V 10   //箱子的总容量 
//物品信息类型声明 
typedef struct{
	int gno;   //物品编号 
	int gv;    //物品体积 
}ElemG;

 //物品结点类型声明
typedef struct node{
 	int gno;
 	struct node* link;
}GoodsLink;
 
 //箱子结点类型声明
typedef struct box{
 	int remainder;   //箱子剩余容量 
 	GoodsLink *hg;
 	struct box *next;
}BoxLink; 
 
 
 //对物品体积降序排序（冒泡排序） 
 void BubbleSort(ElemG *g,int n){
	ElemG temp;
 	for(int i=0;i<n;i++){
		for(int j=n-1;j>i;j--){
			if(g[j].gv>g[j-1].gv){
				temp=g[j];
				g[j]=g[j-1];
				g[j-1]=temp;
			}
		}
	}
 } 
 
 //把物品装入箱子中 
 BoxLink* PackingBox(ElemG *g,int n){
 	BoxLink * hbox,*p,*tail;     //hbox为箱子链表的头指针，tail为尾指针，p用来遍历链表和创建箱子结点 
 	GoodsLink *q,*newg;      //q用来遍历物品链表，newg用来创建物品结点 
 	hbox=NULL;
	for(int i=0;i<n;i++){
		for(p=hbox;p&&p->remainder<g[i].gv;p=p->next);   //遍历链表，寻找能放下目前最大体积的物品的结点 
		if(!p){                          //如果已有箱子放不下该最大体积的物品，就创建一个容量为V的空箱子结点 
			p=(BoxLink*)malloc(sizeof(BoxLink));
			p->next=NULL;
			p->hg=NULL;
			p->remainder=V;
			if(!hbox)      //如果创建的箱子结点为头结点 
			hbox=tail=p;
			else
			tail=tail->next=p;
		}

		newg=(GoodsLink*)malloc(sizeof(GoodsLink));   //创建一个物品结点 
		newg->link=NULL;
		newg->gno=g[i].gno;                    //存入目前最大体积的物品的编号 
		for(q=p->hg;q&&q->link;q=q->link);     //遍历物品链表 
		if(!q){               //如果要插入的物品结点为物品链表的头结点 
			p->hg=newg;       //将该结点尾插 
		}else{
			q->link=newg;
		}
		p->remainder-=g[i].gv;  //物品结点放入箱子结点以后，将该箱子结点剩余容量减去放入的物品的体积 
	} 
 	return hbox;
 }
 
  
 //输出每个箱子存放物品的编号 和剩余容量 
 void PrintLink(BoxLink* hbox,int n){
 	int i=1;
 	BoxLink *p;
 	GoodsLink *q;
 	for(p=hbox;p;p=p->next){
 		printf("第%d个箱子：",i++);
 		for(q=p->hg;q;q=q->link){
 			printf("\t物品编号为%d",q->gno);
		}
		printf("\t剩余容量为：%d",p->remainder);
		printf("\n");	
	}
 	
 }
 

 
 
 int main(void){
 	ElemG *g;
 	BoxLink *hbox;
 	int n;
 	printf("请输入要放入的物品数量：");
	scanf("%d",&n); 
 	g=(ElemG*)malloc(n*sizeof(ElemG));
 	for(int i=0;i<n;i++){
 		g[i].gno=i+1;
 		printf("请输入第%d个物品的体积(物品体积小于10)：",g[i].gno);
 		scanf("%d",&g[i].gv);
 		if(g[i].gv>10){
 			printf("输入物品体积不合法，请重新输入\n");
 			i--;
		}
	}
	  
	BubbleSort(g,n);  //排序 

	hbox=PackingBox(g,n);  //装箱 
	
	PrintLink(hbox,n);  //输出每个箱子存放物品的编号 
 }

 

运行结果如下：