文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 背包问题 课程设计
侵权投诉

背包问题 课程设计

1 需求分析

利用回溯法的设计思想来解决背包问题。首先是将可供选择的物品的个数输入程序,将物品排成一列,计算总物品的体积s,然后输入背包的实际体积V,如果背包的体积小于0或者大于物品的总体积s,则判断输入的背包体积错误,否则开始顺序选取物品装入背包,假设已选取了前i 件物品之后背包还没有装满,则继续选取第i+1件物品,若该件物品"太大"不能装入,则弃之而继续选取下一件,直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包,则说明"刚刚"装入背包的那件物品"不合适",应将它取出"弃之一边",继续再从"它之后"的物品中选取,如此重复,直至求得满足条件的解。

因为回溯求解的规则是"后进先出",所以要用到栈来存储符合条件的解,在存储过程中,利用数组来存储各个物品的体积,然后用深度优先的搜索方式求解,将符合条件的数组元素的下标存入栈里,最后得到符合条件的解并且实现输出。

2 概要设计

使用栈作为该程序的数据结构,利用栈进行语法检查,以深度优先的搜索方式解空间,实现递归过程和函数的调用,在设计时还使用C语言的数组及其循环语言来实现程序。

运用回溯法解题,在搜索解空间树时,只要其左儿子节点是一个可行结点,搜索就进入左子树,在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。具体步骤如下:

(1)针对所给问题,定义问题的解空间; (2)确定易于搜索的解空间结构;

(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索;

上一页第3页

你可能喜欢

  • 农夫过河问题
  • 算法设计论文
  • 约瑟夫环
  • 课程设计说明书
  • 数据结构集合运算的课程设计
  • 数据结构课程设计迷宫求解
  • 背包九讲
  • 贪心算法论文

热门文档

相关文档

  • 背包问题课程设计

    背包问题课程设计_经济学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 背包问题课程设计_经济学_高等教育_教育专区。今日推荐 ...

  • MFC设计背包问题课程设计

    MFC设计背包问题课程设计_计算机软件及应用_IT/计算机_专业资料。MFC设计背包问题课程设计课程设计课程 题目 面向对象程序设计课程设计 背包问题的求解 院系名称 班级...

  • 回溯法背包问题课程设计报告

    实习地点 实训目的: 19~20 计算机学院实验室 周 数 2 通过两周的课程设计,实现回溯法解决背包问题的方法,达到巩固理论知 识、锻炼实践能力、构建合理知识结构的...

  • 0-1背包问题课程设计说明书

    21 II 课程设计说明书(论文)用纸 1 问题描述 (1) 0-1 背包问题:给定 n 中物品和一个背包。物品 i 的重量是 Wi ,其 价值为 Vi ,背包的容量为 C。问:...

  • 软件工程课程设计报告背包问题11

    2012-2013 学年第 1 学期“软件工程”课程设计报告 学院/系 专业 班级 项目名称 组长 小组成员 信息工程学院计算机科学系 计算机科学与技术 24020902 背包问题算法...

  • 枚举,回溯,动态规划解决01背包问题课程设计论文

    枚举,回溯,动态规划解决01背包问题课程设计论文_理学_高等教育_教育专区。枚举,回溯,动态规划解决01背包问题课程设计论文包括算法设计,分析,对比,截图及源代码...

  • 背包问题和棋盘覆盖课程设计报告

    背包问题和棋盘覆盖课程设计报告_理学_高等教育_教育专区。算法分析与设计的课程设计,里面包含两个设计题目:背包问题及棋盘覆盖算法,很好的下载资料……希望大家能够...

  • 数据结构课程设计 背包问题的求解

    如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 数据结构课程设计 背包问题的求解 数据结构课程设计 背包问题的求解数据...

  • 数据结构 课程设计 背包问题&有序顺序表

    数据结构 课程设计 背包问题&有序顺序表_计算机软件及应用_IT/计算机_专业资料。2011级大三课程设计 背包问题&有序顺序表背包问题代码: #define maxsize 1024 #...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email