C language based on greedy algorithm to solve the packing problem

An example of C language based on greedy algorithm to solve the packing problem is presented. To share for your reference, specific as follows:

Problem description:

There are 1 box with a capacity of V and at the same time there are 7en items. Each item has a volume (less than or equal to the box capacity). It is required to pack all the items into the box to minimize the number of boxes occupied.

The greedy algorithm requires that the solution in each step is the best solution in the current step. The solution of the original problem can be achieved by a series 1 locally optimal choice, which does not depend on the solution of the subproblem.

Algorithm idea:

1. Data structure

To solve the number of boxes, that is, you cannot determine how many boxes will be occupied, so you store boxes and their information in the form of a linked list.

At the same time, the number of items in each box cannot be determined. Similarly, linked lists are used to store the information of items in each box.

Thus, the definition of data node is obtained:

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. Solution idea

Keep the number of open boxes as small as possible, which means that the volume of each box is occupied as much as possible. After sorting items in descending order of volume, start with the first item and look for the bins in which it can be placed to ensure local optimality.

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);

Once the sorting is complete, you can officially start packing boxes.

Start every time from the first box, check its remaining volume can still put the current item, can put the best, if not continue to check the remaining capacity of the next box. If all the boxes that have been opened don't fit the current item, open another empty box and stuff it in.

GBox * GoodsBox(Goods goods[], int n)
{
  GNode *h = NULL, *pg, *t;
  GBox *hbox = NULL, *pb, *qb;
  int i;
  for (i = 0; i<n; i++)///////////////// Iterate through the array of goods information 
  {
    pg = (GNode *)malloc(sizeof(GNode));/////////////// Assign cargo node units 
    pg->gno = goods[i].gno;
    pg->link = NULL;// Cargo node initialization 
    if (!hbox)// if 1 Not a single box 
    {
      hbox = (GBox *)malloc(sizeof(GBox));
      hbox->remainder = 10;
      hbox->head = NULL;
      hbox->next = NULL;
    }
    qb=pb = hbox;// All point to the head of the box 
    while (pb)// Looking for a box 
    {
      if (pb->remainder >= goods[i].gv)///////////////////////////// Can hold 
        break;// Find the box and jump out while
      else
      {
        qb = pb;
        pb = pb->next;//qb Is the precursor 
      }
    }///////////////////////////////////// The traversal of the box ends 
    if (pb==NULL)///////////////////// New boxes are needed 
    {
      pb = (GBox *)malloc(sizeof(GBox));// Distribution box 
      pb->head = NULL;
      pb->next = NULL;
      pb->remainder = 10;// The initial volume 
      qb->next = pb;// Precursors to the 
    }
    if (!pb->head)// If the case is out of stock 
    {
      pb->head = pg;
      t = pb->head;
    }
    else
    {
      t = pb->head;
      while (t->link) t = t->link;// pending   The tail plug 
      t->link = pg;
    }
    pb->remainder -= goods[i].gv;
      //////////////////////////////////// packing 
  }
  return hbox;

I hope this article has been helpful in programming C.