装箱问题
2023-04-18 15:02:59 时间
/*
* 装箱问题
* 算法:贪婪
* coder:qpz
* time:2014-11-23
*/
#include <stdlib.h>
#include <iostream>
using namespace std;
#define MAX 20
/*
第一步:创建物品字典
*/
typedef struct {
int gno;//编号
int ver;//占用空间
}Gnode;
Gnode *bh(int n);
void prinGnode(Gnode *a,int n);
/*
第二步:创建箱子
*/
//1.箱子里所装的物品
typedef struct gnode{
int gno;//编号
struct gnode *gnext;//指向物品
}GGnode;
//2.箱子
typedef struct box{
int ver;//箱子体积
GGnode *gnext;//指向箱中物品
struct box *bnext;//指向下一个箱子
}Box;
//打开新箱子
Box *OpenBox(void);
/*
第三步:装箱
贪心算法
*/
Gnode *SortGno(Gnode *a,int n);//排序
GGnode *Put(int gno);// 物品放入箱子
Box *PackingBox(Gnode *a,int n);//处理过程
void prinBox(Box *a,Gnode *dic);//输出箱子信息
/*
free
*/
void takeaway(GGnode *);
void closebox(Box *);
int main(void)
{
Gnode *a,*b;
Box *box;
int n=0;
cout<<"请输入物品个数:";
cin>>n;
if(n){
a=bh(n);
cout<<"排序前";
prinGnode(a,n);
b=SortGno(a,n);
cout<<"排序后";
prinGnode(b,n);
box=PackingBox(b,n);
prinBox(box,a);
closebox(box);
free (a);
free (b);
}else{
cout<<"没有物品,不用打开箱子"<<endl;
}
return 0;
}
//创建物品字典
Gnode *bh(int n)
{
Gnode *a=(Gnode *)malloc(n*sizeof(Gnode));
for(int i=0;i<n;i++){
a[i].gno=i+1;
cout<<"请输入第"<<a[i].gno<<"个物品的体积";
cin>>a[i].ver;
} /*end for*/
cout<<"物品数据库创建成功!!!"<<endl;
cout<<endl;
return a;
}
//输出物品字典
void prinGnode(Gnode *a,int n)
{
cout<<"物品表输出:"<<endl;
for(int i=0;i<n;i++){
cout<<"编号:"<< a[i].gno<<","<<"体积:"<<a[i].ver<<endl;
}/*end for*/
cout<<endl;
}
//排序
Gnode *SortGno(Gnode *a,int n)
{
Gnode *b=(Gnode *)malloc(n*sizeof(Gnode));
Gnode t;
for(int i = 0;i < n; i++){
b[i]=a[i];
}/*end for*/
for(int i=0;i<n;i++){
int max;
for(int j=max=i;j<n;j++){
if(b[j].ver>b[max].ver){
max=j;
}/*end if*/
}/*end for2*/
t=b[i];
b[i]=b[max];
b[max]=t;
}/*end for1*/
return b;
}
//打开新箱子
Box *OpenBox(void)
{
Box *head;
head=(Box *)malloc(sizeof(Box));
head->ver=MAX;
head->gnext=NULL;
head->bnext=NULL;
return head;
}
//放入物品
GGnode *Put(int gno)
{
GGnode *gp=(GGnode *)malloc(sizeof(GGnode));
gp->gno=gno;
gp->gnext=NULL;
return gp;
}
//装箱
Box *PackingBox(Gnode *a,int n)
{
Box *head,*p,*qb;
GGnode *gp,*qg;
head=p=OpenBox();
for(int i = 0;i < n; i++){
//是否超过箱子最大容量 是 箱子装不下 输出编号 continue
if(a[i].ver > MAX){
cout<<"编号为"<<a[i].gno<<"的物品体积过大"<<endl;
continue;
}/*end if*/
qb=p;
//判断已开箱子可否存入
while(p&&(a[i].ver > p->ver)){
qb=p;
p=p->bnext;
} //while
//没有已开箱子可以装下物品
if(!p){
//1.开新箱子
qb->bnext=p=OpenBox();
} /*end if*/
//装箱
//1.修改箱子容量
p->ver-=a[i].ver;
//2.放入物品
for(qg=gp=p->gnext;gp;qg=gp,gp=gp->gnext);
if(!qg)
p->gnext=Put(a[i].gno);
else
qg->gnext=Put(a[i].gno);
}/*end for 遍历物品*/
if(head->ver == MAX){
head=NULL;
}
return head;//箱子头结点地址;
}
//输出箱子信息
void prinBox(Box *a,Gnode *dic)
{
int cnt=0;
for(Box *p=a;p;p=p->bnext){
cout<<"箱子编号:"<<++cnt<<" 箱子剩余空间为:"<<p->ver<<endl;
if(p->gnext){
cout<<"箱子中物品有:"<<endl;
for(GGnode *gp=p->gnext;gp;gp=gp->gnext){
cout<<"物品编号"<<gp->gno<<" 物品体积:"<<dic[gp->gno-1].ver<<endl;
}/*end for in*/
}else{
cout<<"箱子中没有物品"<<endl;
}
cout<<endl;
}/*end for out*/
cout<<"共打开"<<cnt<<"个箱子"<<endl;
}
void takeaway(GGnode *a)
{
GGnode *q;
for(q=a;a;q=a){
a=a->gnext;
free(q);
}/*end for*/
}
void closebox(Box *a)
{
Box *q;
for(q=a;a;q=a){
a=a->bnext;
takeaway(q->gnext);
free(q);
}/*end for*/
}
相关文章
- 工作绩效数据,工作绩效信息和工作绩效报告的区别
- 一段代码解决Colab自动掉线问题,机智到让你意外
- 苹果工程师对iOS线程开发的那点事津津乐道
- 谷歌你变了,老员工痛别谷歌:透明开放不复,文化“面目全非”
- 中国第一批“丁克”晚年,没结婚、没后代是幸福、是感慨、还是咎由自取,自作自受?
- macOS Monterey 与以下电脑兼容下载操作流程解析
- PMP考试之【PMBOK(第六版)49个过程及ITTO】
- SDWebImage从小白到大师蜕变
- C C++内功心法-基础篇
- PMP考试计算题汇总
- Swift进阶-内存管理
- Swift-方法调度-类的普通方法底层探究
- IT人员必须要掌握的几个网络测试命令详解
- OC源码剖析对象的本质
- 微信公众号崩溃了,然后呢?
- 负载均衡的算法你了解不?
- 负载均衡的5种算法,你了解几种?
- .NET Core 的 Docker 容器目录乱码问题
- 使用 HttpClient 进行表单提交时,遇到的问题
- [Abp vNext 源码分析] - 13. 本地事件总线与分布式事件总线 (Rabbit MQ)