贪婪算法及其应用

￡神魔★判官ぃ 2022-06-03 03:52 247阅读 0赞

### 贪婪准则： ###

①贪婪准则设计算法过程的每一步都是最优解（局部最优）

②贪婪准则一旦设好，则固定不变。

③贪婪准则并不一定得到最终最优解（最高效的、最快速的与最优解相近的）

### **应用：** ###

### 问题：装箱问题 ###

①问题描述：

<A>有若干个体积为V的箱子

<B>有n个物品，这n个物品的体积互不相同

V0、V1、V2.......Vn-1

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

②解决：设计贪心准则

<A>将所有的物品，按照体积降序排序

<B>每次取出一个物品（当前未装入箱子中体积最大的）

<C>遍历所有已打开的箱子，将该物品放入一个较早打开的箱子

③演示存储结构图：

![SouthEast][]

![SouthEast 1][]

④算法描述：

<A>创建物品信息数组并初始化

<B>将所有物品按体积降序排序

<C>装箱：

i 遍历箱子链

ii 创建新箱子、初始化箱子、挂箱子

iii 放物品

vi 数箱子

<D>输出已经调整好的箱子

代码实现：

#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 SortD(ElemG *g,int n)
    {
    	ElemG t;
    	int i,j;
    	for(i=0;i<n-1;i++)
    	{
    		for(j=i+1;j<n;j++)
    		{
    			if(g[i].gv<g[j].gv)
    			{
    				t=g[i];
    				g[i]=g[j];
    				g[j]=t;
    			}
    		}
    	}
     } 
     //将物品进行装箱
     BoxLink* packing(ElemG *g,int n)
     {
     	BoxLink *hBox=NULL,*tail,*p;
    	 GoodsLink *q,*newg;
    	 for(int i=0;i<n;i++)
    	 {	
    	 	//遍历所有箱子情况下，寻找合适的箱子
    	 	for(p=hBox;p&&p->remainder<g[i].gv;p=p->next);
    	 	if(!p){
    	 		p=(BoxLink*)malloc(sizeof(BoxLink));
    	 		//箱子初始化 
    	 		p->remainder=V;
    	 		p->hg=NULL;
    			p->next=NULL;
    			//创建第一个箱子 
    	 		if(!hBox) hBox=tail=p;
    	 		//在末尾创建新的箱子 
    	 		else tail=tail->next=p;
    		 }
    		 //将物品放进去后，箱子的剩余体积 
    		 p->remainder-=g[i].gv;
    		 newg=(GoodsLink*)malloc(sizeof(GoodsLink));
    		 //物品链初始化
    		 newg->gno=g[i].gno;
    		 newg->Link=NULL;
    		 //如果物品链为空 
    		 if(!p->hg)  p->hg=newg;
    		 else{
    		 	//物品链不为空，在尾部创建 
    		 	for(q=p->hg;q->Link;q=q->Link) q->Link=newg;
    		 }
    	  } 
    	  return hBox;
      } 
      //输出装好物品的箱子 
      void printBox(BoxLink*h)
      {
      	int i=0;
      	BoxLink*p;
    	GoodsLink *q;
    	//输出相应的箱子 
    	for(p=h;p;p=p->next)
    	  {
    	  	printf("第%d个箱子",++i);
    	  	//输出对应的物品 
    	  	for(q=p->hg;q;q=q->Link)
    	  	printf("%5d",q->gno);
    	  	printf("\n");
    	   } 
      }
      int main(void)
      {
      	ElemG *g;
      	BoxLink *hBox;
      	int n,w;//物品个数
    	//初始化物品信息
    	printf("请输入物品个数：");
    	scanf("%d",&n);
    	g= (ElemG*)malloc(n*sizeof(ElemG));
    	for(int i=0;i<n;i++)
    	{
    		g[i].gno=i+1;//由于物品编号从1开始，在原始数组情况下加1 
    		scanf("%d",&w);
    		g[i].gv=w;
    	}
    	//降序排序
    	SortD(g,n);
    	//装箱
    	hBox=packing(g,n);
    	//输出箱子
    	printBox(hBox);
    	return 0; 
      }

[SouthEast]: /images/20220603/eeb6cd36d338457f982f49155d877556.png
[SouthEast 1]: /images/20220603/4ee4dc29f3e54dacb43d6caac1313521.png