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

杨利霞

! w/ ?9 e0 Y% N1 ^; F" T+ U海底数据中心的散热优化设计，可以用贪心算法装箱问题

/ z5 D; Z, q- Z& H! ?问题描述：

    有一些箱子，容量为V，同时有n个物品，每个物品有一个体积（小于等于箱子容量），要求将物品全部装入箱子中，使占用的箱子数尽量少。
) \$ j" F" {) \. M
: k6 L7 a4 C; H3 Z" t3 p& \' a贪心算法中要求每一步的解都是当前步骤中的最优解。原问题的解可以通过一系列局部最优的选择来达到，这种选择并不依赖于子问题的解。
+ F5 M: g* d: J& ]' W8 _4 `, l$ m
算法思想：

1、数据结构
. }5 z- r2 g/ E9 e# q: s* V
+ F$ q' x2 E3 i# g" s0 J    要求求解箱子数目，也就是说不能确定会占用多少个箱子，因此采用链表的形式来存储箱子及其信息。

    同时，每个箱子中物品的数目也无法确定，同理采用链表来存储每个箱子中的物品信息。

由此得出数据节点的定义：

typedef struct
# D2 z7 f3 R+ p& i{
        int gno;
        int gv;
& @) T: N& Y$ k% q6 q: I}Goods;
* m  W/ A* s( Otypedef struct node
{
        int gno;
        struct node *link;
}GNode;
typedef struct node1
{
        int remainder;
" s0 L; Y' O; X        GNode * head;
- I2 O6 S" }6 T! Y% a. ]0 T        struct node1 * next;
}GBox;
" }9 U7 F: |9 K
2、求解思路
    使打开的箱子数尽量少，也就是说每个箱子容积被尽可能多地占用。将物品按照体积降序排列后，再从第一个物品开始，挨个寻找能放下它的箱子，这样可以保证局部最优。
1 Y+ u% d6 d2 e6 n/ _. _
<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++)
& H! M" Z* f2 }) p        {
                for (j = i + 1; j<n; j++)
                {
                        if (goods[i].gv<goods[j].gv)
2 b& n% I% z3 _+ H% e- F/ q                        {
                                t = goods[i];
                                goods[i] = goods[j];
                                goods[j] = t;
                        }
1 R: E4 l# n5 _9 k                }
$ j7 L9 K4 k. y8 S8 h$ E        }
+ E. b1 b+ M& P0 m5 y; @! [        for (i = 0; i<n; i++)
- A5 x& J. D6 N                printf("%d   %d\n", goods[i].gno, goods[i].gv);

0 q/ k: d2 Y, y: |8 }! X
" _; U7 f( f% T( H  t$ d排序完成，就可以正式开始装箱子了。
9 n$ P! H6 R. g7 Z9 G/ [; X& U5 N每次都从第一个箱子开始，查看它的剩余容积还能不能放下当前的物品，能放下最好咯，放不下的话就继续查看下一个箱子的剩余容量。如果所有的已经打开的箱子都放不下当前的物品，那就只好再打开一个空箱子，把它塞进去。


GBox * GoodsBox(Goods goods[], int n)
{
4 K  X* e: ?6 G# I" Z/ n/ ^) n6 d        GNode *h = NULL, *pg, *t;
4 {6 `$ _: S; e% A/ ]. w) k        GBox *hbox = NULL, *pb, *qb;
        int i;
# |/ {! R7 a* d9 N3 D        for (i = 0; i<n; i++)/遍历货物信息数组
        {
                pg = (GNode *)malloc(sizeof(GNode));///分配货物节点单元
8 N: t; I5 \, k- w                pg->gno = goods[i].gno;
                pg->link = NULL;//货物节点初始化
                if (!hbox)//若一个箱子都没有
                {
9 z9 `, B$ J1 P3 t+ A+ ]                        hbox = (GBox *)malloc(sizeof(GBox));
3 c1 G# |9 N: \6 K, p& D8 @                        hbox->remainder = 10;
, \. x  O; g/ Z2 c5 B! z                        hbox->head = NULL;
                        hbox->next = NULL;
                       
                }
                qb=pb = hbox;//都指向箱子头
                while (pb)//找箱子
/ X$ m8 o/ a6 D0 E1 A2 n0 f9 R                {
9 ~8 F) h+ h2 T& _% N5 U  H                        if (pb->remainder >= goods[i].gv)/能装下
                                break;//找到箱子，跳出while
                        else
- j3 y" M5 l3 ?6 B2 Q                        {

. v5 U7 Q! e8 ~* p# L: ~& y                                qb = pb;
6 c  t) X1 y6 n9 a8 D                                pb = pb->next;//qb是前驱
                        }
' t5 p) k& t8 x3 c
                }/遍历箱子结束
/ m& K/ N) ~. _, A) A                if (pb==NULL)/需要新箱子
$ o6 u+ y# \- k0 O* L; {2 S                {
! x. ~( ?9 o7 v4 L8 |4 y                        pb = (GBox *)malloc(sizeof(GBox));//分配箱子
                        pb->head = NULL;
                        pb->next = NULL;
                        pb->remainder = 10;//初始体积
% s6 K/ d+ X5 C# z  B0 t: J. }" T                        qb->next = pb;//前驱指上
$ q/ x7 y' g+ ~  y                       
% i4 C- s& B' A9 c1 ~2 V" \; [
( U7 E$ n# V9 Q4 p8 c6 e9 I                }
/ B0 l/ Y2 W- l# P& Q6 a2 v                if (!pb->head)//如果箱子里没货
: F+ i, q0 S/ m" ~9 A- C+ @                {
9 U! }" Z3 \0 Q, n' s1 C% i                        pb->head = pg;
$ D, r  S# _: Q5 I, J# H* d' u$ A) }                        t = pb->head;
                }
                else
                {
" v4 }: M5 ?0 q1 l                        t = pb->head;
) B  j; V. `4 r1 u! v% Q7 l                        while (t->link) t = t->link;//货尾  尾插
+ v5 {0 q5 l2 G$ }5 f; R                        t->link = pg;
                }
- b# @; \' N7 F  w8 o                pb->remainder -= goods[i].gv;
0 U, _' s. M3 z                       
/ y  R- A6 [6 ~  M, Y- _                        装箱
3 F, P/ i5 I* q
) d& M6 I- w7 ^1 _; B        }

————————————————
版权声明：本文为CSDN博主「祝大余」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Panda_m/article/details/41599423
/ T) T" ^5 J5 F# y4 K$ H3 ]/ [