与利润有关的背包问题.doc

大学 学院计算机程序训练任务书学生姓名： 班级： 学号： 设计题目 ：与利润有关的背包问题 一，题目：与利润有关的背包问题二，问题描述：输入N种货物重量w kg及获利p，输出各种货物及重量到文件。题目解释：一个商人带着一个能装m kg的背包去乡下收购货物，准备将这些货物卖到城里获利。现有n种货源，且知第i种货物有wi kg，可获利pi元。请编写算法帮助商人收购货物，以获取最高的利润。三，系统设计说明：1 系统用到的数据类型程序设计一般由两部分组成：算法和数据结构，合理地选择和实现一个数据结构和处理这些数据结构具有同样的重要性，在与利润有关的背包问题中，由于需要各种数据，所以需要定义各种数据的类型。主要包括如下：#includestdio.h#define N 30typedef struct int bh;float m;float h;float l;2、main()主函数程序采用函数调用的设计理念，主函数程序的入口，各调用函数均由主函数控制调用。控制功能的实现通过循环执行一个开关语句，该语句的条件值是通过调用主菜单得到的返回值（head）,根据该值，调用相应的各功能函数。3printf()输出函数 直接利用输出函数printf输出字符串，在屏幕上显示一个菜单。四，功能本程序功能是输入N种货物重量w kg及获利p，输出各种货物及重量到文件，通过C语言程序最终帮助商人获取最大利润1.N-S图：定义宏替换#define N 30 定义一个结构体变量B，组成成员分别有bh,m,h,l,输入信息数组m的值for(i=0;im;i+bi.bh=i+1输入第n个质量 m 即bi.m输入第n个获利h 即bi.hbi.l=bi.h|bi.m 输入背包的质量X for(i=o;i=m-1;i+); for(j=i+1;jbi.l Y N cent=bi bi=bj bj=cent for(n=0;n+); (x-=bn.m)0 Y N Break for(i=0;ibi.l)cent=bi;bi=bj;bj=cent;使bi和bj的值互换以达到l降序排列的目的。8. if(x-=bn.m)0)break;使选择货物的质量不能超过背包的质量。9.最后利用语句y+=bi.h;使利润进行累加，最终输出最大利润。六，源程序#includestdio.h#define N 30typedef struct int bh;int m;int h;float l; B;main()B bN,cent;int i,a,j,n;int x,y=0;printf(要输入货物的种类数：n);scanf(%d,&a);for(i=0;ia;i+)bi.bh=i+1;printf(请输入第%d种货物的质量m: ,bi.bh);scanf(%d,&bi.m);printf(请输入第%d种货物获利h: ,bi.bh);scanf(%d,&bi.h);bi.l=bi.h/bi.m;printf(输入背包最大载重x: );scanf(%d,&x);for(i=0;ia-1;i+)for(j=i+1;jbi.l)cent=bi;bi=bj;bj=cent;for(n=0;n+)if(x-=bn.m)0)break;printf(收购第：);for(i=0;in;i+)printf(%3d,bi.bh);y+=bi.h;printf(种货物可获最高利润：%dn,y);七，参考文献 c程序设计（第三版） 谭浩强编 清华大学出版社2006年 算法设计与分析 吕国英 清华大学出版社2003年 八，结束语通过这次C语言程序设计课程的一次全面的综合性上机实验，我得到了宝贵的经验，在编写程序的过程