#include<conio.h>
#include<string>
using namespace std;

typedef struct goods /*物品结构信息*/
{
      int goodsNo; /*物品编号*/
      struct goods *link; /*另一个物品的指针*/
}GOODS;

typedef struct box /*箱子结构信息*/
{
      int remain_space; /*箱子的剩余空间*/
      GOODS * head; /*箱内物品链表的头指针*/
      struct box *next; /*箱子链表的后继箱子指针*/
}BOX;

int main(void)
{
      int n, /*物品的个数*/
          box_count, /*箱子个数*/
          box_volume, /*箱子的容积*/
          *goods_volume, /*存储各个物品体积信息的动态数组*/
          i;
      BOX *box_h, /*装箱链表首节点指针*/
          *box_t, /*装箱链表尾节点指针*/
          *box_u;
      GOODS *p_goods, /*当前将装箱的物品节点*/
            *q_goods; /*指向装箱链表的当前箱子的最后一个物品*/
          
      printf("请输入箱子的容积： ");
      scanf("%d", &box_volume);
      printf("\n请输入物品的数量: ");
      scanf("%d", &n);
      goods_volume = (int *)malloc(sizeof(*goods_volume) * n); /*存储物品体积信息的数组*/    
      printf("\n请按重大到小的顺序输入物品的体积:\n");
      for(i = 0; i < n; i++)
      {
          printf("物品[%d]的体积为：",i+1);
          scanf("%d", goods_volume + i);
      }

      box_h = box_t = NULL; /*预置已用箱子链表为空*/
      box_count = 0; /*预置已用箱子箱子计数器为空*/
    
      /*下面将物品i装箱*/
      for(i = 0; i < n; i++)
      {
          /*从[已用的]第一只箱子开始顺序寻找能放入物品i的箱子j;*/
          p_goods = (GOODS *)malloc(sizeof(GOODS));
          p_goods->goodsNo = i; /*物品编号*/
          p_goods->link = NULL;
          for(box_u = box_h; box_u != NULL; box_u = box_u->next)
          {
              if(box_u->remain_space >= goods_volume[i]) /*找到还可装入物品i的箱子[box_u指针指向它]*/
              {
                  break;
              }
           }
        
           if(box_u == NULL) /*已用箱子都不能装入物品i,或装箱链表为空*/
           {
              box_u = (BOX *)malloc(sizeof(BOX)); /*使用一只新的空箱来装载物品i*/
              box_u->remain_space = box_volume - goods_volume[i]; /*计算新箱子的剩余空间*/
              box_u->next = NULL;
              box_u->head = NULL; /*新箱子尚未装入一件物品*/
              if(box_h == NULL)
              {
                  box_h = box_t = box_u; /*本次装入的物品是当前箱子的第一个物品*/
              }
              else
              {
                  box_t = box_t->next = box_u; /*将本次装入的物品挂接在当前箱子的物品装箱链表的末尾*/
              }
              box_count++; //*累加所用箱子计数器*/
          }
          else
          {
              box_u->remain_space = box_u->remain_space - goods_volume[i]; /*将物品i装入已用箱子中*/
          }
        
          /*将物品i挂接到当前箱子的物品装箱链表中*/
          /*让指针q_goods指向装箱链表中的当前箱子的最后一个物品*/
          for(q_goods = box_u->head; q_goods != NULL && q_goods->link != NULL; q_goods = q_goods->link);
          if(q_goods == NULL) /*最后一个物品为空,当前物品i装入的箱子box_u是新创建的箱子*/
          {
              p_goods->link = box_u->head;
              box_u->head = p_goods; /*新箱子box的物品链首节点指针指向物品节点p_goods*/
          }
          else
          {
              p_goods->link = NULL;
              q_goods->link = p_goods; /*物品i挂接到当前箱子box的最后一个物品q_goods之后*/
          }
      }

      /*输出结果*/
      printf("\n一共使用 %d只箱子\n", box_count);
      printf("各箱子所装物品情况为:\n");
      for(box_u = box_h, i = 1; box_u != NULL; box_u = box_u->next, i++) /*第i只箱子情况*/
      {
          printf("\n第%2d 只箱子剩余空间为 %4d, 所装物品为: ", i, box_u->remain_space);
          for(p_goods = box_u->head; p_goods != NULL; p_goods = p_goods->link)
          {
              printf("%4d", p_goods->goodsNo + 1);
          }
          printf("\n");
      }
        
      free(goods_volume);
      getch();
    
      return 0;
}