本篇文章为大家展示了怎么在C语言中利用贪心算法解决装箱问题,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。
站在用户的角度思考问题,与客户深入沟通,找到普陀网站设计与普陀网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都做网站、成都网站设计、企业官网、英文网站、手机端网站、网站推广、主机域名、网页空间、企业邮箱。业务覆盖普陀地区。算法思想:
1、数据结构
要求求解箱子数目,也就是说不能确定会占用多少个箱子,因此采用链表的形式来存储箱子及其信息。
同时,每个箱子中物品的数目也无法确定,同理采用链表来存储每个箱子中的物品信息。
由此得出数据节点的定义:
typedef struct { int gno; int gv; }Goods; typedef struct node { int gno; struct node *link; }GNode; typedef struct node1 { int remainder; GNode * head; struct node1 * next; }GBox;
2、求解思路
使打开的箱子数尽量少,也就是说每个箱子容积被尽可能多地占用。将物品按照体积降序排列后,再从第一个物品开始,挨个寻找能放下它的箱子,这样可以保证局部最优。
void GoodsSort(Goods goods[], int n) { int i, j; Goods t; for (i = 0; i排序完成,就可以正式开始装箱子了。
每次都从第一个箱子开始,查看它的剩余容积还能不能放下当前的物品,能放下最好咯,放不下的话就继续查看下一个箱子的剩余容量。如果所有的已经打开的箱子都放不下当前的物品,那就只好再打开一个空箱子,把它塞进去。
GBox * GoodsBox(Goods goods[], int n) { GNode *h = NULL, *pg, *t; GBox *hbox = NULL, *pb, *qb; int i; for (i = 0; igno = goods[i].gno; pg->link = NULL;//货物节点初始化 if (!hbox)//若一个箱子都没有 { hbox = (GBox *)malloc(sizeof(GBox)); hbox->remainder = 10; hbox->head = NULL; hbox->next = NULL; } qb=pb = hbox;//都指向箱子头 while (pb)//找箱子 { if (pb->remainder >= goods[i].gv)/////////////////////////////能装下 break;//找到箱子,跳出while else { qb = pb; pb = pb->next;//qb是前驱 } }/////////////////////////////////////遍历箱子结束 if (pb==NULL)/////////////////////需要新箱子 { pb = (GBox *)malloc(sizeof(GBox));//分配箱子 pb->head = NULL; pb->next = NULL; pb->remainder = 10;//初始体积 qb->next = pb;//前驱指上 } if (!pb->head)//如果箱子里没货 { pb->head = pg; t = pb->head; } else { t = pb->head; while (t->link) t = t->link;//货尾 尾插 t->link = pg; } pb->remainder -= goods[i].gv; ////////////////////////////////////装箱 } return hbox; C语言是什么
C语言是一门面向过程的、抽象化的通用程序设计语言,广泛应用于底层开发,使用C语言可以以简易的方式编译、处理低级存储器。
上述内容就是怎么在C语言中利用贪心算法解决装箱问题,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注创新互联网站建设公司行业资讯频道。
另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
标题名称:怎么在C语言中利用贪心算法解决装箱问题-创新互联
网页路径:http://bzwzjz.com/article/ghgdc.html