算法设计与分析课程设计报告.doc

《算法设计与分析课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、下载可编辑课程设计报告课程设计名称：算法设计与分析系：三系学生：吴阳班级：12软件(2)班学号：20120311232成绩：指导教师：秦川开课时间：2014学年一学期.专业.整理.下载可编辑一、问题描述1．普通背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品，使得装入背包中的物品的总价值最大，在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。2．0/1背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品，使得装入背包中的物品的总价值最大，在选

2、择物品i装入背包时，对于每种物品i只有两种选择，即装入背包或者不装入背包，不能将物品装入背包多次，也不能只装入部分的物品i。3．棋盘覆盖问题在一个2kx2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。二、问题分析1．普通背包问题对于背包问题，若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量Ｗ，剩余的将是n-1个原重物品1，2，······.专业.整理.下载可编辑，j-1，j+1，·····，n以及重为Ｗi－Ｗ的物品j中可装入容量为C－Ｗ的背包且具有最

3、大价值的物品。2．0/1背包问题如果当前背包中的物品的总容量是cw，前面的k-1件物品都已经决定好是否要放入包中，那么第k件物品是否放入包中取决于不等式cw+wk<=M(其中，wk为第k件物品的容量，M为背包的容量)（此即约束条件）然后我们再寻找限界函数，这个问题比较麻烦，我们可以回忆一下背包问题的贪心算法，即物品按照物品的价值/物品的体积来从大到小排列，然后最优解为（1，1，1.......，1，t，0，0，......），其中0<=t<=1；因此，我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下)，我们可以考虑我们能够达到的最大的价值，即我们可以通

4、过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。通过该条件，可以减去很多的枝条，大大节省运行时间。3．棋盘覆盖问题.专业.整理.下载可编辑每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角方格的行列坐标，然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。在递归函数里，还要

5、有一个变量s来记录边的方格数，每次对方块进行划分时，边的方格数都会减半，这个变量是为了方便判断特殊方格的位置。其次还要有一个变nCount来记录L型骨牌的数量。三、建立数学模型1．普通背包问题普通背包问题的数学描述为：在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。C>0,wi>0,vi>0,1≤i≤n,要求找出一个n元0-1向量（x1,x2,x3,·····，xn）,xi∈{0,1}，1≤i≤n,使得≤C,而且达到最大。2．0/1背包问题0-1背包问题的数学描述为：不能将物品装入背包多次，也不能只装入部分的物品i。C>0,wi>0,vi>0

6、,1≤i≤n,要求找出一个n元0-1向量（x1,x2,x3,·····，xn）,xi∈{0,1}，1≤i≤n,使得≤C,而且达到最大。3．棋盘覆盖问题当k>0时，将2k×2k棋盘分割为4个2^k-1×2^k-1子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。.专业.整理.下载可编辑四、算法设计1．普通背包问题因为每一个物品都可以分割成单位块，单位块的

7、利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解决。算法设计：首先计算每种物品单位重量的价值Vi/Wi，然后按单位重量价值从大到小进行排序，根据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。或将这种物品全部装入背包后，背包的物品总重量未超过背包容量C，则选择单位重量价值次高的物品并尽可能多地装入背包，依此策略一直进行下去，直到背包装满为止。2．0/1背包问题该0-1背包问题采用的是回溯算法，回溯算法的基本解题步骤是：（1）针对所给问题定义问题的解空间；（2）确定