服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - C语言基于贪心算法解决装箱问题的方法

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

2021-06-26 14:33忆之逸之 C/C++

这篇文章主要介绍了C语言基于贪心算法解决装箱问题的方法,简单描述了装箱问题,并结合实例形式给出了C语言使用贪心算法解决贪心问题的相关操作技巧,需要的朋友可以参考下

本文实例讲述了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

延伸 · 阅读

精彩推荐