怎么在C语言中利用贪心算法解决装箱问题-创新互联

本篇文章为大家展示了怎么在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://www.cdkjz.cn/article/ghgdc.html