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

-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)当表中没有元素时称为空栈，用Top=1表示；

(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。流程图如下：Push(进栈)a0a1……an-1Pop(出栈)top(栈顶)回溯法：三总体设计使用语言：Java界面化展示：Android实现方法利用回溯法的设计思想来解决背包问题。首先将物品排列成一列，然后顺序选取物品装入背包，假设已选取了前i件物品后背包还没装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而选取下一件，直到背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明上一个装入背包的物品在此种情况下不是最优选择，将其去掉形成新的栈，继续再从他下一个物品中选取，如此重复，直到求得满足条件的解，或者无解。由于回溯法求解的规则是“后进先出”因此自然要用到栈。（1）主要功能模块实现递归参数确定:数据位置，当前结果集总重量物品数据通过List方式存储，每个物品都存在两个属性，“编号”和“是否用过”。那么，每次递归首先要记录的就是本次操作执行时，当前的操作数编号。以编号方式代替数据，类似于数据库中的数据id亦或是Map映射中的key与value的关系。其次，每次操作主要是重量的比较，那么，当前结果集的重量和剩余重量都是重要参数，由于整体操作是向结果数据及栈中增加数据，每次操作是与背包容量进行比较，因此，选择当前结果集总重量。递归主体：得到当前栈中的最后一个数的数据位置，和当前结果集总重量，从上一个位置开始遍历，遍历剩余的产品，如果此数在备选项中且没有被使用，同时，此物品重量小于或等于背包容量，则将此物品的序号计入相应的位置数组中，继续向下执行，如果当前结果集总重量加上此物品重量刚好等于背包容量，者通过位置数组输出数据，这便是一组符合要求的结果，如果不等，设置此数据为被使用并将当前结果总重量和位置加一递归此函数。递归堆栈演示图：演示数据：背包重量5物品重量1，2，3，4得到第一组结果：（1，4）一次循环结束，进行下一次循环，第一次进入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展示。五系统调试过程测试数据：背包总量20产生随机数个数10产生的随机数：1,2,4,9,10,10,13,16,17,17输出结果：(12413)(1217)(1910)(416)递归次数：39递归中间量变化：1nowSum01num12nowSum12num23nowSum33num34nowSum74num45nowSum165num56nowSum176num57nowSum127num48nowSum138num49nowSum169num410nowSum1910num411nowSum511num312nowSum1412num413nowSum1513num414nowSum1814num415nowSum1015num316nowSum1116num317nowSum1417num318nowSum1718num319nowSum1819num320nowSum220num221nowSum621num322nowSum1522num423nowSum1623num424nowSum1924num425nowSum1125num326nowSum1226num327nowSum1527num328nowSum1828num329nowSum1929num330nowSum430num231nowSum1331num332nowSum1432num333nowSum1733num334nowSum934num235nowSum1935num336nowSum1036num237nowSum1337num238nowSum1638num239nowSum1739num2六使用过程输入数据点击产生随机数。点击产生结果，跳转产生的结果集。七总结