1、数据结构与算法设计课程设计任务书题 目 背包问题的求解软件学生姓名 刘永超 学号 200901030114 专业班级 数学 0901设计内容与要求【问题描述】假设有一个能装入总体积为 T 的背包和 n 件体积分别为 S1 , S2 , , Sn 的物品，能否从 n 件物品中挑选若干件恰好装满背包，即使 S1 +S2 + + Sn=T，要求找出所有满足上述条件的解。例如：当 T=10，各件物品的体积1，8，4，3，5，2时，可找到下列 4 组解：（1，4，3 ，2） （1，4，5）（8，2） （3，5，2） 。【软件功能】设计一个背包问题的求解软件, 解决背包刚好装满的问题；【算法思想】1：本求
2、解背包问题的软件设计，采用“图”作为策略搜索的逻辑结构，2：以栈做工具解决背包问题的求解，借用“图“ 的深度优先搜索和回朔法实现求解的过程，3：用非递归和递归两种方法来求解背包问题；（利用图形用户界面显示结果）4：在非递归算法中用深度优先搜索来搜索总是首先搜索下面一步的所有可能情况，然后再进一步考虑后面的各种情况。判断是否有解。5：由于回溯求解的规则是“后进先出”因此自然要用到栈。主要的算法操作有：1：深度优先搜索的方案 public void bagProblem()2：显示背包求解结果方案 public void DisplayRoute();3：初始化背包图形界面 public void
3、 Init()；4：在递归算法中递归求解的算法：private boolean bag(int s, int n) 5：物品放入背包的算法：public void push(int j)6：判断背包是否为空的算法:public boolean isEmpty()【提交成果】1.“数据结构与算法设计课程设计任务书”一份，打印装袋；2.“数据结构与算法设计课程设计报告”一份，打印装袋；3、上面两项内容的 word 文档，通过电子邮件交到指导教师。起止时间 2012 年 6 月 18 日 至 2012 年 7 月 1 日指导教师签名 李元觉 2012 年 6 月 18 日 系（教研室）主任签名 郝华宁 2012 年 6 月 18 日学生签名 刘永超 2012 年 6 月 20 日注明：内容限 1 页
