美文网首页
装箱问题

装箱问题

作者: Simple_a | 来源:发表于2019-03-12 22:50 被阅读0次

贪心算法

 优点:简单,高效
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);

    
}

相关文章

  • 装箱问题

    问题 假设有编号分别为0、1、……、n-1的n种物品,体积分别为V0、V1、……、Vn-1。将这n种物品装到容量都...

  • 装箱问题

    贪心算法 装箱问题 问题描述: 求解思路: 代码实现:

  • 深入剖析Java中的装箱和拆箱

    自动装箱和拆箱问题是Java中一个老生常谈的问题了,今天我们就来一些看一下装箱和拆箱中的若干问题。本文先讲述装箱和...

  • 0007-装箱问题

    问题描述 一个工厂制造的产品形状都是长方体,它们的高度都是 h,长和宽都相等,一共有六个 他们的长宽分别为 1...

  • 世界级难题:把不同物品装进箱子,如何使箱子表面积最小?

    ​导读:三维装箱问题是一类经典的组合优化问题,具有巨大的学习研究和实际应用价值。传统的三维装箱问题都是给定了箱子的...

  • 是时候告诉你集装箱超重该怎么解决咯?

    大连海事局查获全国最大一起集装箱严重超重!如何处理集装箱超重问题?下面由Candy来给大家说明一下情况。 集装箱本...

  • 二手住人集装箱多少钱?使用方便吗?

    二手住人集装箱多少钱?使用方便吗?侨诺制造教你如何解决集装箱定制排水问题? 由于集装箱定制的柜子都是密封的,对于居...

  • 一些三维装箱问题

    三维装箱问题在电商业务中有重要应用, 例如订单打包和商品装车. 下面我们列举一些电商业务中可能用到的三维装箱问题....

  • 现在越来越多的消费者选择购买住人集装箱

    如今,越来越多的消费者选择购买住人集装箱屋,因为集装箱被广泛应用于各个领域。集装箱成本多少也成为许多用户关注的问题...

  • Openjudge noi 19 装箱问题

    题目: 描述一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为11...

网友评论

      本文标题:装箱问题

      本文链接:https://www.haomeiwen.com/subject/nyzopqtx.html