本文实例讲述了C语言基于贪心算法解决装箱问题的方法。分享给大家供大家参考,具体如下:
问题描述:
有一些箱子,容量为V,同时有n个物品,每个物品有一个体积(小于等于箱子容量),要求将物品全部装入箱子中,使占用的箱子数尽量少。
贪心算法中要求每一步的解都是当前步骤中的最优解。原问题的解可以通过一系列局部最优的选择来达到,这种选择并不依赖于子问题的解。
算法思想:
1、数据结构
要求求解箱子数目,也就是说不能确定会占用多少个箱子,因此采用链表的形式来存储箱子及其信息。
同时,每个箱子中物品的数目也无法确定,同理采用链表来存储每个箱子中的物品信息。
由此得出数据节点的定义:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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、求解思路
使打开的箱子数尽量少,也就是说每个箱子容积被尽可能多地占用。将物品按照体积降序排列后,再从第一个物品开始,挨个寻找能放下它的箱子,这样可以保证局部最优。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void GoodsSort(Goods goods[], int n) { int i, j; Goods t; for (i = 0; i<n - 1; i++) { for (j = i + 1; j<n; j++) { if (goods[i].gv<goods[j].gv) { t = goods[i]; goods[i] = goods[j]; goods[j] = t; } } } for (i = 0; i<n; i++) printf ( "%d %d\n" , goods[i].gno, goods[i].gv); |
排序完成,就可以正式开始装箱子了。
每次都从第一个箱子开始,查看它的剩余容积还能不能放下当前的物品,能放下最好咯,放不下的话就继续查看下一个箱子的剩余容量。如果所有的已经打开的箱子都放不下当前的物品,那就只好再打开一个空箱子,把它塞进去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
GBox * GoodsBox(Goods goods[], int n) { GNode *h = NULL, *pg, *t; GBox *hbox = NULL, *pb, *qb; int i; for (i = 0; i<n; i++) /////////////////遍历货物信息数组 { pg = (GNode *) malloc ( sizeof (GNode)); ///////////////分配货物节点单元 pg->gno = 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语言程序设计有所帮助。
原文链接:https://blog.csdn.net/panda_m/article/details/41599423