c语言装箱问题思路 C语言基于贪心算法解决装箱问题的方法

本文实例讲述了C语言基于贪心算法解决装箱问题的方法。分享给大家供大家参考，具体如下：

问题描述：

有一些箱子，容量为V，同时有n个物品，每个物品有一个体积(小于等于箱子容量)，要求将物品全部装入箱子中，使占用的箱子数尽量少。

贪心算法中要求每一步的解都是当前步骤中的最优解。原问题的解可以通过一系列局部最优的选择来达到，这种选择并不依赖于子问题的解。

算法思想：

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

{

for (j = i + 1; j

{

if (goods[i].gv

{

t = goods[i];

goods[i] = goods[j];

goods[j] = t;

}

}

}

for (i = 0; i

printf("%d %d\n", goods[i].gno, goods[i].gv);

排序完成，就可以正式开始装箱子了。

每次都从第一个箱子开始，查看它的剩余容积还能不能放下当前的物品，能放下最好咯，放不下的话就继续查看下一个箱子的剩余容量。如果所有的已经打开的箱子都放不下当前的物品，那就只好再打开一个空箱子，把它塞进去。

GBox * GoodsBox(Goods goods[], int n)

{

GNode *h = NULL, *pg, *t;

GBox *hbox = NULL, *pb, *qb;

int i;

for (i = 0; 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语言程序设计有所帮助。