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

下载后可任意编辑用 c 语言解决背包可行解问题学生姓名：漆巧 指导老师：卢曼莎 摘 要 本课程设计是为了解决假设有一个能装入总体积为 T 的背包和 n 件体积分别为 w1 , w2 , … , wn 的物品，能否从 n 件物品中选择若干件恰好装满背包，即使 w1 +w2 + … + wn=V，要求找出所有满足上述条件的解。在课程设计中，系统开发平台为 windowsxp，程序设计设计语言采纳 C 语言，程序运行平台为 windows xp。设计中，对于背包问题，主要采纳递归的思想。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在实际生活中。关键词 枚举；回溯法；动态规划；栈；递归1 引言 本课程设计是为了解决旅行者的背包问题。将分别采纳枚举；回溯；动态规划三种方法去设计。通过对这三种方法的应用，可以更好的解决类似的问题。同时采纳栈作为该程序的数据结构，利用栈进行语法检查，深度优先的搜索方式解空间，实现递归过程和函数的调用，在设计时还使用 c 语言的数组及其循环语言来实现程序。1下载后可任意编辑1.1 课程设计目的 讨论应用递归思想，背包算法。应用数据结构基础知识进行实际问题求解与分析。编程实现算法。1.2 课程设计的方法 本课程设计采纳枚举，回溯，动态规划三种方法解决常见的背包问题。例如用回溯法解题，在搜索解空间树时，只要其左子节点是一个可行节点，搜索就进入左子树，在右子树可能包含最优解是才进入右子树搜索。否则将右子树剪去。具体步骤如下：（1）针对所给问题，定义问题的解空间；（1）确定易于搜索的解空间结构（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避开无效搜索。1.3 系统的开发平台在课程设计中，系统开发平台为 windows xp， 课程设计设计语言采纳 C 语言，程序运行平台为 windows xp。2 整体设计流图2.1 本课题设计所用数据结构以及流程图背包问题求解涉及到的数据结构主要是栈，下面我就详细的介绍一下有关栈方面的知识。栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。当用一维数组存储栈时，被称为顺序栈。 (1)通常称插入、删除的这一端为 栈顶（Top），另一端称为栈底（Bottom）；2下载后可任意编辑 (2)当表中没有元素时称为空栈，用 Top==-1 表示； (3)栈为后进先出（Last In First Out）的线性表，简称为 LIFO 表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元...