用c语言解决背包问题正文

1初步实现了设计目标，并且经过适当完善后，将可以应用在实际生活中。本课程设计是为了解决旅行者的背包问题。将分别采用枚举；回来实现程序。研究应用递归思想，背包算法。应用数据结构基础知识进行实际分析。编程实现算法。2本课程设计采用枚举，回溯，动态规划三种方法解决常见的背包问题。例如入左子树，在右子树可能包含最优解是才进入右子树搜索。否则将右子树剪去。具体步骤如下：（1）针对所给问题，定义问题的解空间；（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。在课程设计中，系统开发平台为windowsxp，关栈方面的知识。栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。当用一维数组存储栈时，被称为顺序栈。（Bottom(2)当表中没有元素时称为空栈，用Top=(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。3最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。栈的修后才能删除。流程图如下：栈的基本运算：（1）InitStack（S）（3）StackFull（S）注意：该运算只适用于栈的顺序存储结构。退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。（6）StackTop（S）4取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。它适用于解一些组合数较大的问题。高搜索的效率，即启发式的搜索。可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组5明无解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组用这类问题的上述性质而提出来的比枚举法效率更高的算法。6否否否是否是本算法采用先进后出的算法来一个一个测试可行的全部解，所以很显然要用到栈。我通过建立顺序表来录入我要输入的各个物体的体积，然后通过sum比我预定的目标体积小，那就继续入栈，有合适的组合则输出，否则说明刚才选入的物体体积即栈最顶端的那个不适合导致后面没有合适的解，所做栈底的所有情况满足后，我们就要考虑以第二个物体为栈底的情况，其实我并没有把第一个物体出栈，只是我读的时候把第一个物体“屏蔽”了，也就是说它虽然在栈中，但是我不考虑它，而是考虑新的栈也就是总栈中截取的7那么就没有物体可以作为参数入栈或出栈了，所有循环结束。本算法采用3重while循环嵌套来实现算出所有不重复的解。typedefstruct{}seqlist;typedefstruct{}seqstack;{s=newseqstack;//{printf("空间不足");//若无法生成结构体，则输出“空间不足”8{s->top=-1;//}{if(s->top==-1)}intpush_seqstack(seqlist*l,inti,seqstack*s){return0;//栈满，无{s->data[s->top]=i;s->sum=s->sum+l->data[i];9}{return0;//栈空，无元{*x=s->data[s->top];s->sum=s->sum-l->data[s->data[s->top]];/s->top--;//栈内元素个数减1}}{seqlist*l;intx=1;l=newseqlist;//\n------------------\n"scanf("%d",&x);while(x!=0)//输入元素不为{l->last++;//没输入}}程序调试成功。在课程设计代码调试过程中也出了不少差错，比如头文件很容易忽略，同学指出才发现；一些符号，像“；”也很容易拉克服了。在此过程中我学到了不少调试的技巧，极大得丰富了编程的知识，这些在程序的优化方面帮助很大。通过此次课程设计的实践，感触较深。不仅使我加深了对书本知识的理解，而且锻炼了我编写程序、调试程序的能力，学习文档编写规范，培养独立学习、地方考虑的还不够周到。在本课题中，我们研究了如何用遗传算法求解组合优化问题中的背包问题，背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题，其计算复杂度为，传统上采用动态规划来求解。背包问题就是在资源有限的条件下，是我们将来的学习中需要改进和加强的地方。现出栈，所以也算是其中的遗憾。源程序代码：{{intw[size];intV;intk=0;inti=0;intj=1;printf("\n请输入可供选择装入物品的个数：");printf("\n请输入各件物品的体积：");printf("\n可供选择的物品的总体printf("\n请输入背包的总体积：");printf("\n输入背包体积错误");printf("\n");{{{}}{printf("第%d个符合条件的解：",j);{}j++;printf("\n");}k=stack.data[--stack.to}Abstract:Basedonthecomprehensiveanalysisontheplasticpart’sstructuresermoundingqualityandmouldmenufactoringsidecorepullingwasdesigned.Byadoptingthcore-pulling.Acorrespondinginjectionmworkingprocessofthemouldwasintroduced在程序中，可能需要为某些整数定义一个别名，我们可以利用预处理指令#define来完成这项工作，您的代码可能是：{(1)枚举型是一个集合，集合中的元素(枚举成员)是一些命名的整型常量，元素之间用逗号,隔开。(2)DAY是一个标识符，可以看成这个集合的名字，是一个可选项，即是可有可无的项。(4)可以人为设定枚举成员的值，从而自定义某个范围内的整数。(5)枚举型是预处理指令#define的替代。(6)类型定义以分号;结束。新的数据类型定义完成后，它就可以使用了。我们已经见过最基本的数据类型，如：整型int,单精度浮点型float,数据类型声明变量通常是这样：doubleresult;/既然枚举也是一种数据类型，那么它和基本数据类型一样也可以对变量进行声明。{enumDAYtomorrow;//变enumDAYgood_day,bad_day;//变方法二：类型定义与变量声明同时进行：enum//跟第一个定义不同的是，此处的标号DAY省略，这是允许的。{enumweek{Mon=1,Tue,Wed,Thu,FriSat,Sun}days;//变量days的类型为枚举型enumweekenumBOOLEAN{false,true}end_flag,match_flag;//定义枚举类型并声明了两个枚举型变量方法三：用typedef关键字将枚举类型定义成别名，并利用该别名进行变量声明：typedefenumworkday{workdaytoday,tomorrow;//变量today和tomorrow的类型为枚举型workday，也即enumtypedefenum{workdaytoday,tomorrow;//变量today和tomorrow的类型为枚举型workday，也即enum也可以用这种方式：typedefenumworkday{workdaytoday,tomorrow;//变量today和tomorrow的类型为枚举型workday，也即enum量。错误示例如下所示：typedefenum{typedefenumWEEK{typedefenum{typedefenumWEEK{3.1对枚举型的变量赋值。实例将枚举类型的赋值与基本数据类型的赋值进行了对比：{enumDAYyesterday,today,printf("%d%d%d\n",yesterday,today,tomorrow);}{intx=10,y=20,z=30;printf("%d%d%d\n",yesterday,today,tomorrow);}方法三：定义类型的同时声明变量，然后对变量赋值。/*定义枚举类型，同时声明该类型的三个{printf("%d%d%d\n",x,y,z);//输出：10printf("%d%d%d\n",yesterday,today,tomorrow);//输出：123}方法四：类型定义，变量声明，赋初值同时进行。/*定义枚举类型，同时声明该类型的三个变量，并赋{}yesterday=MON,today=TUE,tomorrow=WE{printf("%d%d%d\n",x,y,z);//输出：10printf("%d%d%d\n",yesterday,today,tomorrow);//输出：123}3.2对枚举型的变量赋整数值时，需要进行类型转换。{enumDAYyesterday,today,tomorrow=(enumDAY)30;////tomorrow=3;//错误printf("%d%d%d\n",yesterday,today,tomorrow);//输出：2330}{NEWLINEVTAB='\r',{charstr[]="I'mElyefod";countofletter++;{countofspace++;}printf("%s%dtimes%c",match_flag?"mprintf("countofletters:%d%c%c",countofletter,NEWLINE,RETURN);}输出：{NEWLINEVTAB='\r',='\n',='\v',{printf("%dbytes\n",sizeof(enumescapes));//4bytesprintf("%dbytes\n",sizeof(escapes));//4bytesprintf("%dbytes\n",sizeof(enumBOOLEAN));//4bytesprintf("%dbytes\n",sizeof(BOOLEAN));//4byte