算法分析和设计课程设计报告.docVIP

目 录 一、问题描述 1 1、普通背包问题 1 2、0-1背包问题 1 3、棋盘覆盖问题 1 二、问题分析 2 1、普通背包问题 2 2、0-1背包问题 2 3、棋盘覆盖问题 3 三、算法设计 3 1、普通背包问题 3 2、0-1背包问题 4 3、棋盘覆盖问题 4 四、算法实现 6 1、普通背包问题 6 2、0-1背包问题 8 3、棋盘覆盖问题 10 五、测试分析 11 1、普通背包问题 11 2、0-1背包问题 13 3、棋盘覆盖问题 15 六、结论 16 七、源程序 17 1、普通背包问题 17 2、0-1背包问题 20 3、棋盘覆盖问题 24 八、参考文献 26 一、问题描述 1、普通背包问题 有一个背包容量为C，输入N个物品，每个物品有重量S[i]，以及物品放入背包中所得的收益P[i]。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪心算法解决。 2、0-1背包问题 在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi, 价值为pi。对于可行的背包装载，背包中的物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高， 即 取得最大值。约束条件 =c和 。在这个表达式中，需求出xixi=1表示物品i装入背包中，xi=0表示物品i不装入背包。 3、棋盘覆盖问题 在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 二、问题分析0或者大于物品的总重量weight，则判断输入的背包重量错误，否则开始顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品太大不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出弃之一边，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解。 因为回溯求解的规则是后进先出，所以要用到栈来存储符合条件的解，在存储过程中，利用数组来存储各个物品的体积，然后用深度优先的有哪些信誉好的足球投注网站方式求解，将符合条件的数组元素的下标存入栈里，最后得到符合条件的解并且实现输出。 3、棋盘覆盖问题 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是： 左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格； 右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格； 左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格； 右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格。 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。 三、算法设计(为了贪心选择准备) 然后，依次将单位价值大的物品放入背包（贪心选择），直到背包放满为止； 在向背包放置物品的过程中，如果 用一维数组x[n] (x[i]∈{1,2, … ,n})，保存问题的解；weight[]存储物品重量; price[]存储物品价值。 2、0-1背包问题 1）基本思路： ①确定问题的解空间，并将解空间组织成易于有哪些信誉好的足球投注网站的子集树的形式； 图4.1解空间树 ②以深度优先的方式有哪些信誉好的足球投注网站整个解空间，遇到不满足约束要求的节点就回溯，沿另一个分支继续有哪些信誉好的足球投注网站；约束函数剪枝，不能超载，超载就回溯。 3、棋盘覆盖问题 1）问题分解过程如下： 以k=2时的问题为例，用二分法进行分解，得到的是如下图4-8，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如图4-8中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个①号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如4-8右图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。 图4.2 图4.3 从以上例子还可以发现，当残缺方格