查看: 7109|回复: 0

海底数据中心的散热优化设计，可以用贪心算法装箱问题（包含代码））

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2021-4-15 16:22 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

海底数据中心的散热优化设计，可以用贪心算法装箱问题

问题描述：

有一些箱子，容量为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、求解思路
使打开的箱子数尽量少，也就是说每个箱子容积被尽可能多地占用。将物品按照体积降序排列后，再从第一个物品开始，挨个寻找能放下它的箱子，这样可以保证局部最优。

<span style="font-family:FangSong_GB2312;">void GoodsSort(Goods goods[], int n)</span>
{
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);

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

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;

装箱

}

————————————————
版权声明：本文为CSDN博主「祝大余」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Panda_m/article/details/41599423