贪心算法--装箱问题

问题描述

n个物品体积分别为：V1、V2、…、Vn。将这n个物品装入若干个体积为V的箱子（约定每个物品的体积Vi都不超过V）。要求：使用的箱子尽可能少。

贪心准则

1）将所有物品按体积大小降序排列；
2）每次都保证将未放入箱子中体积最大的物品优先放入已打开的箱子中。

存储结构

分析：
物品个数固定，采用数组存储；所需箱子个数不确定，箱子采用链表存储；每个箱子里能装的物品个数也不确定，同样采用链表存储。
1）物品
形式：数组（goods）
类型：物体编号（gno）、物体体积（gv）—>结构体变量GOODS
2）箱子
形式：链表（hg）
类型：剩余体积（remainder）、指向物品结点的头指针（hg）、指向下一个箱子的指针域（next）—>结构体变量BOX
3）物品链结点
形式：链表（head）
类型：物品编号（gnum）、指向下一个物品的指针域（link）—>结构体变量GNODE

简述算法实现

按照物品体积降序排列之后，每拿出一个物品，从第一个箱子开始遍历，寻找能装下的那个箱子，装箱；再拿下一件物品。。。直至物品全部装箱。最终实现的结果大致如下：
示意图：

若要查找每个箱子装的物品编号，遍历其hg域指向的物品链即可。

C代码实现

#include <stdio.h>
#include <stdlib.h>
 
#define V 10
 
typedef struct goods{   //物品存储结构
    int gno;    //物品编号
    int gv;     //物品体积
}GOODS;
 
typedef struct gnode{   //物品链结构
    int gnum;   //物品编号
    struct gnode* link; //指向下一物品
}GNODE;
 
typedef struct box{ //箱子链结构
    int reminder;   //剩余空间
    GNODE* hg;  //头指针
    struct box* next;   //指向下一箱子
}BOX;
 
void sort(GOODS* goods,int n)
{   //按物品体积降序排序
    int i,j;
    GOODS t;
    for(i=0;i<n;i++)
        for(j=i;j<n;j++)
            if(goods[i].gv<goods[j].gv)
            {
                t=goods[i];
                goods[i]=goods[j];
                goods[j]=t;
            }
}
 
BOX* intoBox(GOODS* goods,int n)
{
    int i;
    BOX* head=NULL;
    BOX *l,*k;
    GNODE *p,*q;
    for(i=0;i<n;i++)
    {
        p=(GNODE*)malloc(sizeof(GNODE));
        p->gnum=goods[i].gno;
        p->link=NULL;
        for(l=head;l&&l->reminder<goods[i].gv;l=l->next);
        if(!l)
        {
            l=(BOX*)malloc(sizeof(BOX));
            l->hg=NULL;
            l->next=NULL;
            l->reminder=V;
            if(!head)
                head=k=l;
            else
                k=k->next=l;
        }
        l->reminder=l->reminder-goods[i].gv;
        for(q=l->hg;q&&q->link;q=q->link);
        if(!q)
            l->hg=p;
        else
            q->link=p;
 
    }
    return head;    
}
 
void printAns(BOX* head)
{
    GNODE* a;
    BOX* b;
    int i=0;
    for(b=head;b;b=b->next)
    {
        printf("这是第%d个箱子，里面装有：",++i);
        for(a=b->hg;a;a=a->link)
            printf("%d号箱子、",a->gnum);
        printf("\n");
    }
}
 
int main(void)
{
    GOODS* goods;
    BOX* box;
 
    int i,n;
    printf("请输入要装箱的物品个数：");
    scanf("%d",&n);
    goods=(GOODS*)malloc(n*sizeof(GOODS));
    for(i=0;i<n;i++)
    {
        goods[i].gno=i+1;
        printf("输入第%d个物品的体积",i+1);
        scanf("%d",&goods[i].gv);
    }
 
    sort(goods,n);  //按物品体积降序排序
 
    box=intoBox(goods,n);   //将物品装入箱子
 
    printAns(box);  //输出装箱结果
 
    return 0;   
}