欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

贪心算法----装箱问题

程序员文章站 2022-06-04 10:52:26
...

贪心准则:
1.将一个问题的几步的每一步抽象出公共的最优解
2.一个问题只有一个贪心准则(问题求解时,贪心准则不能改变)
特点
不一定可以产生最优解
好处:
简单快速
需求描述:
有N个物品,体积V1,V2,V3,V4….Vn,若干个体积为v的箱子。
问题:把所有的物品装进箱子中,使得打开的箱子尽量小。
思路:
1.将所有的物品按照体积的降序排列
2.按照箱子的打开顺序遍历已打开的箱子,将物品装入一个较早打开的箱子中。
图示:
贪心算法----装箱问题
代码描述:

#include<stdio.h>
#include<stdlib.h>
#define V 10
//定义物品
typedef struct {
    int gno;//商品编号
    int gv;//商品体积
}EGoods;
//定义物品链
typedef struct goods{
    int gno;//商品编号
    int gv;//商品体积
    struct goods *link;//商品链
}GoodsLink;
//箱子
typedef struct box{
    int restv;//箱子剩余体积
    GoodsLink *hg;//用来挂物品链
    struct box *next;//箱子链
}BoxLink;
//将物品按体积的降序排序
void sort(EGoods g[], int len){
    for (int i = 0; i < len - 1; i++){
        for (int j = i + 1; j < len; j++){
            if (g[i].gv < g[j].gv){
                EGoods t = g[i];
                g[i] = g[j];
                g[j] = t;
            }
        }
    }
}
//装箱函数
BoxLink* packingBox(EGoods g[], int len){
    sort(g, len);
    GoodsLink *tailgoods = NULL;
    BoxLink *hbox = NULL, *pbox = NULL, *tailbox = NULL;
    for (int i = 0; i < len; i++){
        //通过循环找到物品应该放的箱子中
        for (pbox = hbox; pbox&&pbox->restv < g[i].gv; pbox=pbox->next);
        if (!pbox){
            //如果该物品是第一个放入箱子中的
            //之前打开的箱子都装不下当前物品
            //打开新箱子
            pbox = (BoxLink*)malloc(sizeof(BoxLink));
            //初始化箱子
            pbox->hg = NULL;
            pbox->next = NULL;
            pbox->restv = V;
            if (!hbox)//如果是第一个箱子
            {
                hbox = pbox;
                tailbox = pbox;
            }
            else{
                tailbox->next = pbox;
                tailbox = tailbox->next;
            }
        }
        //生成当前物品
        GoodsLink *newq = (GoodsLink*)malloc(sizeof(GoodsLink));
        newq->gno = g[i].gno;
        newq->gv = g[i].gv;
        newq->link = NULL;  
        //利用循环找到当前物品在箱子中的位置(找到箱子链的为节点,之后进行挂链)
        for (tailgoods = pbox->hg; tailgoods&&tailgoods->link; tailgoods = tailgoods->link);
        if (!tailgoods){
            pbox->hg = newq;
        }
        else{
            tailgoods->link = newq;
        }
        pbox->restv -= g[i].gv;
    }
    return hbox;
}
//打印箱子
void print(BoxLink *hbox){
    int count = 0;//记录箱子号
    for (BoxLink *pb = hbox; pb; pb = pb->next){
        printf("箱子号:%d\n",++count);
        for (GoodsLink *pg = pb->hg; pg; pg = pg->link){
            printf("物品编号:%d,体积:%d\t", pg->gno, pg->gv);
        }
        printf("\n");
    }
}
int main(void){
    int v[10] = { 3, 2, 5, 8, 4, 7, 6, 9, 1, 10 };
    EGoods g[10];
    for (int i = 0; i < 10; i++){
        g[i].gno = i + 1;
        g[i].gv = v[i];
    }
    print(packingBox(g, 10));
    system("pause");
    return 0;
}

运行结果:
贪心算法----装箱问题