[置顶] 装箱问题

   1  问题分析   

       这次我听老范了讲了装箱的问题,题目:有n个物品,体积为v1,v2,v3. . .然后要求用最少的箱子把这些物品里面,这个是基于贪心算法的思想。贪心算法呢,就是每次找到的都是当前最优的,但是最后从整体情况看,它不1定是最优的;贪心算法规则1旦建立,就不能更改。1般情况下贪心算法求的解都是最优解。、

         我们先对物品进行从大到小进行排序,每次拿出1个物品从第1个箱子开始遍历,如果可以放下,那末重新拿出1个物品在从第1个开始遍历,如果放不下,那末我们就开1个新箱子,将这个物品放在里面。其实这个思想很简单的,最简单的说我每次拿出1个物品都是从第1个箱子开始,放的下,拿下1个物品,放不下,开新箱子,每次遍历的是箱子。

        还有1种思路呢,就是每次遍历的是物品。意思就是呢,我拿出1个箱子,开始遍历物品(物品体积都是从大到小),遍历完1次物品后第1个箱子就表示装满了,然后在开辟第2个箱子,知道所有的物品装完为止。

       存储 : 对物品个数我们是固定的的,可以用数组来寄存。而对箱子呢,我们不知道到底要用多少个箱子,因此呢箱子的个数我们用链表去寄存。每一个箱子里面装的物品个数也不肯定,那末也用链表来处理。我们可以用3个结构体,第1个结构体箱子信息,第2个结构体物品信息,第3个结构体箱子中的物品的信息

2 代码区

 

   

#include <iostream>
#include<stdlib.h>
#define null NULL
#define V 10
typedef struct{ //物品信息的结构体
int go; //编号
int gv; //体积
}GOODS;

typedef struct Gnode{ // 物品节点
int gnum; // 挂在链上的编号
struct Gnode *link; //指向下1个物品节点
}GNODE;

typedef struct Gbox{ // 箱子结构体
int reminder; //剩余空间
GNODE *head; // 指向物品节点的第1个节点
struct Gbox *next;

}GBOX;

void sortvolume(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;
}
}

GBOX *packingbox(GOODS *goods,int n){ //具体实现装箱

int i;
GBOX *hb=null,*ht,*p;
GNODE *newg,*q;

for(i=0;i<n;i++){

newg=(GNODE*)malloc(sizeof(GNODE));
newg->gnum=goods[i].go;
newg->link=null;

for(p=hb;p&&p->reminder<goods[i].gv;p=p->next); //p停下来时1定的总是开辟新箱子,分号注意

if(!p)
{
p=(GBOX *)malloc(sizeof(GBOX));
p->head=null;
p->next=null;
p->reminder=V;

if(!hb)
hb=ht=p;
else
ht=ht->next=p;
}

p->reminder-= goods[i].gv;
for(q=p->head;q&&q->link;q=q->link);// 特别注意

if(!q)
p->head=newg;
else
q->link=newg;

}

return hb;

}

void printpackingbox(GBOX *hbox) //输出
{
GBOX *p;
GNODE *q;
int i=0;
for(p=hbox;p;p=p->next)
{
printf("这是第%d个箱子,里面有",++i);
for(q=p->head;q;q=q->link)
{

printf("编号为%d",q->gnum);

}
printf("
");
}

}

int main(int argc, char** argv){ //主函数

int n;
GOODS *goods;
GBOX *hbox;

printf("请你输入物品的个数: ");
scanf("%d",&n);
goods=(GOODS *)malloc(n*sizeof(GOODS));
for(int i=0;i<n;i++){
printf("输入第%d个物品的体积是",i+1);
scanf("%d",&goods[i].gv);
goods[i].go=i+1;

}
sortvolume(goods,n);

hbox=packingbox(goods,n); //箱子的头结点

printpackingbox(hbox); //输出

return 0;
}

3  示意图

       箱子挂上物品后就是这个模样

   
4 分析代码

       现在有很多
排序方法,选择,插入,快排,冒泡,归并随意写1个就好。

       这个程序有几处特别好,不知道你们看没有看出来,2个for语句循环里面是空的,for(p=hb;p&&p->reminder<goods[i].gv;p=p->next);   这个分号特别注意,不管我开不开新箱子,我总会用1个p指针来处理箱子的问题,而p停的地方就是当前这个物品1定可以放进去的,如果p为空。我就开新箱子放,如果p不为空,直接放进去。利用一样的思路,我就只用1个q指针很好的处理了装在箱子里面的物品链,不管头不为空。q停下的地方1定可以把该物品挂在后面,for(q=p->head;q&&q->link;q=q->link);(分号特别注意)我利用了尾插法,有人会问为何不用头插法,缘由是虽然这样好处理,但是这样物品就被倒着放在里面了。

        这次我还知道了,尽量使for循环里面嵌套if else 不要在if else 里面嵌套for循环,由于1般是大时间复杂度嵌套小的。

5  运行结果

      注意箱子设的最大体积是10,不可以超过10

 

      

        如果里面有甚么毛病,或甚么建议,欢迎大家提出来

         

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » [置顶] 装箱问题

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡