C 언어 는 욕심 알고리즘 을 바탕 으로 포장 문 제 를 해결 하 는 방법

본 고 는 C 언어 가 욕심 알고리즘 을 바탕 으로 포장 문 제 를 해결 하 는 방법 을 실례 로 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
질문 설명:
일부 상 자 는 용량 이 V 이 고 n 개의 물품 이 있 으 며,각 물품 은 하나의 부피(상자 용량 보다 작 음)가 있 으 며,물품 을 모두 상자 에 넣 어 점용 하 는 상자 수 를 최대한 적 게 하도록 요구한다.
욕심 산법 에서 모든 단계 의 해 를 요구 하 는 것 은 현재 절차 에서 가장 좋 은 해 이다.원래 문제 의 해 는 일련의 국부 적 으로 가장 좋 은 선택 을 통 해 이 루어 질 수 있 는데 이런 선택 은 하위 문제 의 해 에 의존 하지 않 는 다.
알고리즘 사상:
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<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
", goods[i].gno, goods[i].gv);

정렬 이 완료 되면 정식으로 상 자 를 담 을 수 있 습 니 다.
매번 첫 번 째 상자 부터 남 은 용적 이 현재 의 물건 을 내 려 놓 을 수 있 는 지 확인 하 는 것 이 가장 좋 습 니 다.내 려 놓 을 수 없 으 면 다음 상자 의 남 은 용량 을 계속 확인 하 세 요.만약 이미 열 린 모든 상자 가 현재 의 물건 을 놓 을 수 없다 면,빈 상 자 를 하나 더 열 어 그것 을 쑤 셔 넣 을 수 밖 에 없다.

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 언어 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.