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

《用c语言解决背包问题正文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、用C语言解决背包可行解问题学生姓名：漆巧指导老师：卢曼莎摘要本课程设计是为了解决假设有一个能装入总体积为T的背包和n件体积分别为w1,w2，...，wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+...+wn=V，要求找出所有满足上述条件的解。在课程设计中，系统开发平台为windowsxp，程序设计设计语言采用C语言，程序运行平台为windowsxp。设计中，对于竹包问题，主要采用递归的思想。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在实际生活中。关键词枚举；回溯法；动态规划；栈；递归1引

2、言本课程设计是为了解决旅行者的背包W题。将分别采用枚举；回溯；动态规划三种方法去设计。通过对这三种方法的应用，可以更好的解决类似的问题。同时采用栈作为该程序的数据结构，利用栈进行语法检查，深度优先的搜索方式解空间，实现递归过程和函数的调用，在设计时还使用c语言的数组及其循环语言来实现程序。1.1课程设计目的研究应用递归思想，背包算法。应用数据结构基础知识进行实际问题求解与分析。编程实现算法。1.2课程设计的方法本课程设计采用枚举，回溯，动态规划三种方法解决常见的背包问题。例如用回溯法解题，在搜索解空间树时，只要其左子节点是一个可行节点

3、，搜索就进入左子树，在衣子树可能包含最优解是冰进入衣子树搜索。否则将衣子树剪去。具体步骤如下：(1)针对所给问题，定义问题的解空问；(1)确定笏于搜索的解空间结构(3)以深度优先的方式搜索解空问，并且在搜索过程中用剪枝函数避免无效搜索。1.3系统的开发平台在课程设计中，系统开发平台为windowsxp，课程设计设计语言采用C语言，程序运行Y•台为windowsxp。2整体设计流2.1本课题设计所用数据结构以及流程背包问题求解涉及到的数据结构主要是栈，下面我就详细的介绍一下奋关栈方面的知识。栈(Stack)是限制仅在表的一端进行插入和删

4、除运算的线性表。当用一维数组存储栈时，被称为顺序栈。(1)通常称插入、删除的这一端为栈顶(Top)，另一端称为栈底(Bottom);(2)当表中没有元素吋称为空栈，用Top=-1表示；(3)栈为后进先出(LastInFirstOut)的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈屮”最新”的元素，即最厄插入(进栈)的元素，而最先插入的是被放在栈的底部，耍到最盾才能删除。栈为P进先出(LastInFirstOut)的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除(退栈)的总是

5、当前栈屮"最新"的元素，即最后插入(进栈)的元素，而最先插入的是被放在栈的底部，要到最后冰能删除。流程阁如T:Push(进栈)aOalan-1top(栈顶)栈的基本运算：(1)InitStack(S)构造~个空栈S。(2)StackEmpty(S)判栈空。若S为空栈，则返回TRUE,杏则返回FALSE。(3)StackFull(S)判栈满。若S为满栈，则返回TRUE，否则返回FALSE。注意：该运算只适用于栈的顺序存储结构。(4)Push(S,x)进桟。若桟S不满，则将元素x插入S的栈顶。(5)Pop(S)退栈。若栈S非空，则将S的栈

6、顶元素删去，并返回该元素。(6)StackTop(S)取栈顶元素。若栈S非空，则返冋栈顶元素，但不改变栈的状态。回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择K一个候选解;倘若当前候选解除了还不满足问题规模要求外，满足所冇其他要求吋，继续扩人当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求吋，该候选解就是问题的一个解。在冋溯法中，放弃当前候选解，寻找下一个候选解的过程称为冋溯。回溯法是一个既带冇系统性又带冇跳跃性的的

7、搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点吋，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点冋溯。否则，进入该子树，继续按深度优先的策略进行搜索。冋溯法在用来求问题的所冇解时，耍回溯到根，且根结点的所冇子树都已被搜索遍才结束。而回溯法在用來求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索W题的解的算法称为回溯法，它适用于解一些组合数较大的问题。冋溯即是较简单、较常

8、用的搜索策略。全面访问所有可能的情况，分为两种：不考虑给定问题的特冇性质，按事先顶好的顺序，依次运用规则，即肓目搜索的方法；另一种则考虑问题给定的特宥性质，选用合适的规则，提高搜索的效率，即启发式的搜索。可用回溯法求解的