本文共 3331 字,大约阅读时间需要 11 分钟。
/**/ /* 标题:< <系统设计师> >应试编程实例-[递推算法程序设计] 作者:成晓旭 时间:2002年09月14日(18:20:00-20:18:00) 实现“装箱”问题的贪婪算法实现函数 时间:2002年09月14日(22:00:00-23:18:00) 实现“装箱”问题的贪婪算法实现函数 时间:2002年09月14日(18:20:38-22:18:00) 实现“人民币找零”问题的贪婪法解决算法 */ #include " stdio.h " #include " stdlib.h " // :============================“装箱”问题的贪婪法解决算法=========================== /**/ /* 作者:成晓旭 时间:2002年09月14日(18:20:38-20:00:00) 完成“装箱”问题的贪婪法解决算法 =================================================== 问题描述: 设有编号为0,1,2,...,n-1的n个物品,体积分别为v0,v1,v2,...,vn-1, 将这n个物品装到容量都为V的若干个箱子内。约定这n个物品的体积均不超过 V,即对于0<=i <=V。要求用较少的箱子装完这n种物品。 编程思想: 假设每只箱子所装物品用链表来表示,链表首节点指针存入一个结构体中, 结构记录该箱子尚剩余的空间量和该箱子所装物品链表的首指针。 算法描述: { 输入箱子的容积; 输入物品的种类数; 按体积从大到小的顺序输入各个物品的体积; 预置已用箱子链为空; 预置已用箱子计数器box_count为0; for(i=0;i {//物品i按以下步骤装箱; 从已用的第一只箱子开始顺序寻找能放入物品i的箱子j; if(已用箱子都不能再放物品i) { 另用一只箱子,并将物品i放入该箱子里; box_count ++; } else 将物品i放入箱子j里; } } */ // 物品信息结构类型定义 #define RES struct RES RES ... { int order; //物品编号 RES * link; //另一个物品的指针} ; // 装箱信息结构类型定义 #define BOX struct BOX BOX ... { int remainder; //箱子剩余空间 RES *r_head; //箱子所装物品的物品链首节点指针 BOX *link; //箱子链的后续箱子节点指针} ; void Encase_Box() ... { //箱子计数器,箱子体积,物品种类,循环计数器 int box_count,box_volume,category,i; int *array; //存储各个物品体积信息的动态数组 //装箱链表的首节点、尾节点指针,程序处理临时变量指针 BOX *b_head,*b_tail,*box; RES *p_res,*q_res; //当前将装箱的物品节点,指向装箱链表的当前箱子的最后一个物品 printf("输入箱子的容积: "); scanf("%d",&box_volume); printf("输入物品的种类: "); scanf("%d",&category); array = (int *)malloc(category * sizeof(int)); printf("按从大到小的顺序输入各个物品的体积: "); for(i=0;i<category;i++) ...{ printf("物品[%d]的体积 = ",i+1); scanf("%d",array + i); } b_head = b_tail = NULL; //预置已用箱子链表为空 box_count = 0; //预置已用箱子计数器 for(i=0;i<category;i++) ...{ //物品i按以下步骤装箱 //从[已用的]第一只箱子开始顺序寻找能放入物品i的箱子j; p_res = (RES *)malloc(sizeof(RES)); p_res->order = i; p_res->link = NULL; for(box = b_head;box != NULL;box = box->link) ...{ if(box->remainder >= array[i]) break; //找到还可装入物品i的箱子[box指针指向它] } if(box == NULL) ...{ //已用箱子都不能装入物品i,或装箱链表为空 //创建一个新的空箱子来装载物品i box = (BOX *)malloc(sizeof(BOX)); box->remainder = box_volume - array[i]; //计算新箱子的剩余空间 box->link = NULL; box->r_head = NULL; //新箱子尚未装入一件物品 if(b_head == NULL) b_head = b_tail = box; //本次装入的物品是当前箱子的第一个物品 else b_tail = b_tail->link = box; //将本次装入的物品挂接在当前箱子的物品装箱链表的末尾 box_count ++; //累加所用箱子计数器 } else box->remainder = box->remainder - array[i]; //将物品i装入已用箱子box中 //以下11行:将物品i挂接到当前箱子box的物品装箱链表中 //让指针q_res:指向装箱链表中的当前箱子的最后一个物品 for(q_res = box->r_head;q_res != NULL && q_res->link != NULL;q_res = q_res->link); if(q_res == NULL) ...{ //最后一个物品为空,当前物品i装入的箱子box是新创建的箱子 p_res->link = box->r_head; //物品i的link设为NULL box->r_head = p_res; //新箱子box的物品链首节点指针指向物品节点p_res } else ...{ p_res->link = NULL; //物品i的link设为NULL q_res->link = p_res; //物品i挂接到当前箱子box的最后一个物品q_res之后 } } //输出装箱问题的处理结果 printf("用容积这[%d]的箱子[%d]个可装完以上[%d]件物品!",box_volume,box_count,category); printf("各箱子所装物品情况如下: "); for(box = b_head,i=1;box != NULL;box = box->link,i++) ...{ //第i只箱子所装物品情况 printf("第%2d只箱子,还剩余容积%4d,所装物品有: ",i,box->remainder); for(p_res = box->r_head;p_res != NULL;p_res = p_res->link) printf(" 物品号[%d],物品体积[%d] ",p_res->order + 1,array[p_res->order]); printf(" "); }} // :============================“装箱”问题的贪婪法解决算法=========================== int main( int argc, char * argv[]) ... { //Encase_Box(); //Journey_Horse(); Run_Give_Change(); printf(" 应用程序运行结束! "); return 0;} Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=935688