用c语言解决背包问题正文.doc资源-CSDN文库

73 浏览量 2022-12-02 16:23:32 上传评论收藏 144KB DOC 举报

资源推荐

资源详情

资源评论

漆巧《用 C 语言解决背包可行性问题》第 1 页共 25 页

1

用 c 语言解决背包可行解问题

学生姓名：漆巧指导老师：卢曼莎

摘要本课程设计是为了解决假设有一个能装入总体积为 T 的背包和 n 件体积

分别为 w1 , w2 , … , wn 的物品，能否从 n 件物品中挑选若干件恰好装满背包，

即使 w1 +w2 + … + wn=V，要求找出所有满足上述条件的解。在课程设计中，

系统开发平台为 windowsxp，程序设计设计语言采用 C 语言，程序运行平台为

windows xp。设计中，对于背包问题，主要采用递归的思想。程序通过调试运行，

初步实现了设计目标，并且经过适当完善后，将可以应用在实际生活中。

关键词枚举；回溯法；动态规划；栈；递归

1 引言

本课程设计是为了解决旅行者的背包问题。将分别采用枚举；回溯；动态规

划三种方法去设计。通过对这三种方法的应用，可以更好的解决类似的问题。同

时采用栈作为该程序的数据结构，利用栈进行语法检查，深度优先的搜索方式解

空间，实现递归过程和函数的调用，在设计时还使用 c 语言的数组及其循环语言

来实现程序。

1.1 课程设计目的

研究应用递归思想，背包算法。应用数据结构基础知识进行实际问题求解与

分析。编程实现算法。

漆巧《用 C 语言解决背包可行性问题》第 4 页共 25 页

4

（6）StackTop（S）

取栈顶元素。若栈 S 非空，则返回栈顶元素，但不改变栈的状态。

回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，

并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是

解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，

满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前

候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题

的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题

的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向

其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回

溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜

索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解

就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，

它适用于解一些组合数较大的问题。

回溯即是较简单、较常用的搜索策略。全面访问所有可能的情况，分为

两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即

盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提

高搜索的效率，即启发式的搜索。

可用回溯法求解的问题 P，通常要能表达为：对于已知的由 n 元组

（x1，x2，…，xn）组成的一个状态空间 E={（x1，x2，…，xn）∣xi∈Si ，

i=1，2，…，n}，给定关于 n 元组中的一个分量的一个约束集 D，要求 E 中

满足 D 的全部约束条件的所有 n 元组。其中 Si 是分量 xi 的定义域，且 |Si|

有限，i=1，2，…，n。我们称 E 中满足 D 的全部约束条件的任一 n 元组为

问题 P 的一个解。若已有满足约束条件的部分解，不妨设为

（ x1,x2,x3,……xi ）， I<n, 则添加 x(i+1) 属于 s(i+2) ，检查

剩余24页未读，继续阅读

内容反馈

zzzzl333

粉丝: 676
资源: 7万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip