回溯法背包问题程设计报告.doc

编号 学生 实 习 类 别 课程设计 学 生 姓 名 姜兆龙 专 业 软件工程 学 号 110521118 指 导 教 师 崔广才 学 院 计算机科学技术 2013年 1 月 起 止 周 19～20 周 数 2 实习地点 计算机学院实验室 实训目的： 通过两周的课程设计，实现回溯法解决背包问题的方法，达到巩固理论知 识、锻炼实践能力、构建合理知识结构的目的。 实训要求： 利用回溯法解决背包问题 理解堆栈原理，回溯的调用时机和参数确定 实训进度安排及主要内容： 第一周： 分析题目要求，整理思路 理解堆栈和回溯原理 第二周： 编写简单测试程序 界面化 成绩： 指导教师/带队教师（签字） 年 月 日 一 概述 问题：回溯法背包问题求解。 问题描述：假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2），（1，4，5），（8，2），（3，5，2）。 主要解决点：递归函数的递归参数和递归内容 二 设计的基本概念和原理 式中x为0-1决策变量，x=1时表示将物品i装入背包中，x=0时则表示不将其装入背包中。 栈的原理：栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。当用一维数组存储栈时，被称为顺序栈。　　(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）；　　(2)当表中没有元素时称为空栈，用Top1表示；　　(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中必威体育精装版的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。 栈为后进先出（Last In First Out）的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中必威体育精装版的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。流程图如下： Push(进栈) a0 a1 …… a n-1 Pop(出栈) top(栈顶) 一次循环结束，进行下一次循环，第一次进入2作为结果集的第一个数。 产生过程的树状图： （2）Android界面展示设计 在MainActivity中加入输入框，让用户输入背包总量和产生的随机数个数，按钮产生随机数，通过ListView展示，以List数组方式存储并传递给下一层。点击产生结果跳转到下一个Activity进行上诉功能模块操作，并返回结果集给ListView展示。 四 详细设计 主要功能模块详细设计 参数随机数集：通过Random方法产生随机数，用List接收产生的数据。在操作前将List从新排序，消除相同的数据，返回操作后的List的长度作为操作长度。循环给Site位置数组和disUsed使用标记数组初始化。 遍历函数：通过if判断nowSum + goodsList.get(j) == bound，（bound是总重量，nowSum是当前结果集的总重量）满足此种情况时，结果集满足条件。 Android展示模块的详细设计 输入框设计：第一个展示页面显示，加入两个EditText，分别接受背包容量和产生数据量，添加内容改变监听，在onTextChanged（内容改变方法）中加入一个线程，当内容改变时，更新主线程，把产生结果按钮隐藏，清楚产生的随机数据。设置输入框为只能输入数字。 随机数产生设计：添加点击事件监听，加入一个flag标记，如果输入框没有输入数据，展示一个Toast提示用户，并把标记设为false。 当flag为真时，且没有被点击过，进入产生随机数函数，并显示产生结果的跳转按钮。通过ListView展示参数的结果集。 数据展示的界面设计：加入AsyncTask异步加载，在新的线程中进行数据结果产生操作，在开始时显示dialog，完成时消失。产生的结果通过list方式存储，并用listview展示。 五 系统调试过程