贪心算法

 优点：简单,高效
1>.贪狼准则（核心）
    a.贪婪准则计算过程每一步都要求是最优解（局部最优）
    b.贪婪准则一旦被设计，中途不变
2>.贪婪准则并不一定能得到最优解，而只是近似最优

装箱问题

问题描述：

问题描述：有若干个体积为V的箱子，有N个体积不全相同的物品。
          要求将所有物品都装入箱子，并且打开的箱子尽可能少。
        

求解思路：

贪心准则：a.将所有物品都按体积降序排列
             b.每次取出一个物品（当前未装入物体中体积最大的物体）
               遍历所有已经打开的箱子，将物品尽可能放入最早打开的箱子
存储：尾插链表
算法描述：a.创建物品信息并初始化
            b.把所有物品按体积降序排列
            c.装箱
            d.输出

代码实现：

#include<stdio.h>
#include<stdlib.h>

#define V 10 // 每个箱子的体积
#define N 8  // 物品个数

//物品信息
typedef struct{
        int gno;  // 物品编号
        int gv;   // 物品体积
    }ElemG;
//物品节点
typedef struct node{
    int gno;  
    struct node *link; // 指向下个物品节点的指针
}GoodsLink;
//箱子节点
typedef struct box{
    int Remainder;    // 存放箱子剩余体积
    GoodsLink *hg;    // 指向存放物品节点的指针
    struct box *next; // 指向下个箱子节点的指针
}BoxLink;

/*1.创建物品信息并初始化*/
void create(ElemG *g){
    int a[N] = { 1, 2, 3, 4, 5, 6, 7, 8};
    printf("物品体积：");
    for(int i=0; i<N; i++){
        g[i].gno = i+1;
        g[i].gv = a[i];
        printf("%d  ",g[i].gv);
    }
}
/*2.把所有物品按照体积降序排列*/
void sort( ElemG *g){
    ElemG temp; // 用于变量交换
    //冒牌排序
    for(int i=0; i<N -1 ; i++){
        
        for(int j= 0; j<N-1-i; j++ ){
            if(g[j].gv < g[j+1].gv){
                temp = g[j];
                g[j] = g[j+1];
                g[j+1] = temp;
            
            }
        }
    }
}
/*3.装箱*/
BoxLink * packed( ElemG *g){
    
    BoxLink *p, *hbox = NULL, *tail;
    for(int i=0; i<N; i++){
        /*3.1 遍历箱子链,找到可以放下当前物品的箱子*/
        for(p=hbox; p!=NULL&&(p->Remainder)<g[i].gv; p=p->next);

        /*3.2 创建新箱子并初始化*/
        if(p==NULL){
            p = (BoxLink*)malloc(sizeof(BoxLink));
            p->Remainder = V;
            p->hg = NULL;
            p->next = NULL;
            if(hbox==NULL)
                hbox = tail = p;//创建第一个箱子
            else
                tail = tail->next = p;//将新节点挂上，并移动尾指针使其指到新节点上
        }
        /*3.3 开始装箱*/
        p->Remainder = p->Remainder-g[i].gv;//计算箱子剩余的体积
        //放物品
        GoodsLink *ne, *q;
        ne = (GoodsLink *)malloc(sizeof(GoodsLink)); // 创建一个物品节点
        ne->gno = g[i].gno;
        ne->link = NULL;
        if(p->hg==NULL)//装的是新箱子
            p->hg = ne;
        else{          //装的是旧箱子

            for(q=p->hg; q->link; q=q->link);// 向后遍历，找到最后一个物品节点。并将新节点挂到末尾
            q->link = ne;
        }
    }
    return hbox;
}   
/*4.输出*/
void printBox(BoxLink *hbox)
{
    GoodsLink *q;
    BoxLink *p = (BoxLink *)malloc(sizeof(BoxLink));
    int cut = 0;
    for(p=hbox; p!=NULL; p = p->next){
        printf("第%d个箱子: ",++cut);
        for(q=p->hg; q; q=q->link)
            printf("%5d",q->gno);
        printf("\n");
    }
    delete p;
}
int main(void){
    
    // 定义物品信息，并分配内存空间
    ElemG *g;
    g = (ElemG *)malloc(N*sizeof(ElemG));

    //1.创建物品信息并初始化
    create(g);

    //2.把所有物品按照体积降序排列
    sort(g);

    //3.装箱
    BoxLink *hbox = NULL;
    hbox = packed( g);

    //4. 输出放入物品后箱子的情况
    printBox(hbox);

    
}