算法设计_课程设计

课 程 设 计 报 告

课程设计名称：算法设计与分析 系 ： 计算机科学系 学生姓名： 班 级： 学 号：

成 绩： 指导教师：

开课时间： 2013-2014 学年 1 学期

一、问题描述

1、普通背包装载问题

有一个背包容量为C，输入N个物品，每个物品有重量S[i]，以及物品放入背包中所得的收益P[i]。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪心算法解决问题。

2、0-1背包装载问题

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大

3、棋盘覆盖问题

在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

二、问题分析

1、普通背包装载问题：

贪心算法的基本思想：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。

背包问题用贪心算法来解决，先求出每件物品的平均价值即p[i]/s[i]，然后每次选择利润p[i]/s[i]最大的物品装进背包，这样就使得目标函数增加最快，当最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。 2、0-1背包装载问题：

回溯法的基本思想：通过系统地搜索一个问题的解空间来得到问题的解。为了实现回溯，首先需要针对所给问题定义解空间。这个解空间必须至少包含问题的一个解（可能是最优的）， 然后组织解空间，确定易于搜索的解空间结构后，按照深度优先策略从开始结点出发搜索解空间。并在搜索过程中利用约束函数在扩展结点处剪去不满足约束的子树，用目标函数剪去得不到最优解的子树，避免无效搜索。

0-1背包问题的数学描述为：n个物品，物品i的重量是wi、其价值为vi，其中0≤i≤n-1，背包的容量为C。用xi表示物品i被装入背包的情况，如果物品Pi被选中，则xi=1；

否则xi=0。求满足目标函数F?max?xi?0n?1i?vi和约束方程?xi?wi?C的物品组合（x0，

i?0n?1x1，x2，…，xn-1) 与相应的总价值V。 3、棋盘覆盖问题：

分治算法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘，由于棋盘只有一个特殊棋盘，所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘，以便采用递归的方法求解，可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处（要理解这句话），如图(c)所示。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略，直至将棋盘分割为1*1的子棋盘。

三、建立数学模型 1、普通背包问题： 求平均价值即p[i]/s[i]

约束条件：c1<=0 2、0-1背包装载问题：

n个物品，物品i的重量是wi、其价值为vi，其中0≤i≤n-1，背包的容量为C。用x[i]表示物品i被装入背包的情况，如果物品Pi被选中，则xi=1；否则xi=0，用bestx[i]存储第i种物品的最优装载方案。

求相应的总价值cw和总重量cp。 约束条件：目标函数F?max3、棋盘覆盖问题：

(1)棋盘：可以一个二维数组board[size][size]表示一个棋盘，其中，size = 2^k。为了在递归处理的过程中使用同一个棋盘，将数组board设置为全局变量

(2)子棋盘：子棋盘由原始棋盘数组board的行下标tr，列下标tc表示。

(3)特殊方格：用board[dr][dc]表示特殊方格，dr和dc表示该特殊方格的在二维数组board中的下标

(4)L型骨牌：一个（2^k）*（2^k）的棋盘中有一个特殊方格，所以用到L型骨牌的个数为（4^k - 1）/3，将所有L型骨牌从1开始连续编号，同一个骨牌有3个方格组成，这3个方格用同一个编号。

?xi?0n?1i?vi和约束方程?xi?wi?C

i?0n?1

四、算法设计 1、普通背包装载问题：

用贪心算法进行设计，贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能 再继续前进时，算法停止。

int n 物品个数 double C 背包的容量 double s[i] 物品的重量（或大小） double p[i]物品的价值

void average(int n,double s[M],double p[M])//按照价值密度的降序排列函数； double c1 背包剩余容量 totalp 物品的总价值

void bag(int n,double C,double s[M],double p[M],double x[M])求物品总价值的函数

在求物品总价值函数中要调用average函数，在主函数中调用bag()函数。

2、0-1背包装载问题，算法步骤如下：

a. 物品有n种，背包容量为C，分别用p[i]和w[i]存储第i种物品价值重量，用 x[i]标记第i种物品是否装入背包，用bestx[i]存储第i种物品的最优装载方案；

b. 用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树（形式参数i表示递归深度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前最优总价值）： ① 若i >n，则算法搜索到一个叶结点，判断当前总价值是否最优： 1> 若cp>bestp，更新当前最优总价值为当前总价值（即bestp=cp），更新 装载方案（即bestx[i]=x[i]( 1≤i≤n)）；

② 采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）： 1> x[i]=j；

2> 若总重量不大于背包容量（即cw+x[i]*w[i]<=c），则更新当前总价 br=\值和总重量（即cw+=w[i]*x[i],cp+=p[i]*x[i]）, 对物品i+1调用递归函 数Backtrack(i+1,cp,cw) 继续进行装载；

3> 函数Backtrack(i+1,cp,cw)调用结束后则返回当前总价值和总重量 （即 cw-=w[i]*x[i],cp-=p[i]*x[i]）； 4> 当j>1时，for循环结束；

③ 当i=1时，若已测试完所有装载方案，外层调用就全部结束；

c. 主函数调用一次backtrack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestp和bestx[i]即为所求最大总价值和最优装载方案。

3、棋盘覆盖问题：

void chessBoard(int tr, int tc, int dr, int dc, int size) { 。。。

if(dr

else {

board[tr+s-1][tc+s-1]=t;/ /覆盖1号三格板 chessBoard(tr, tc, tr+s-1, tc+s-1, s); //覆盖其余部分 }

if(dr=tc+s) //残缺棋盘位于右上棋盘 chessBoard(tr, tc+s, dr, dc, s); else {

board[tr+s-1][tc+s]=t; //覆盖2号三格板 chessBoard(tr, tc+s, tr+s-1, tc+s, s); //覆盖其余部分 }

if(dr>=tr+s && dc

board[tr+s][tc+s-1]=t; //覆盖3号三格板 chessBoard(tr+s, tc, tr+s, tc+s-1, s); //覆盖其余部分 }

if(dr>=tr+s && dc>=tc+s) //残缺方格位于右下棋盘 chessBoard(tr+s, tc+s, dr, dc, s); else {

board[tr+s][tc+s]=t; //覆盖4号三格板 chessBoard(tr+s, tc+s, tr+s, tc+s, s);//覆盖其余棋盘 }

五、测试分析

测试数据，测试输出的结果；复杂度分析；每个模块设计和测试时存在问题的(问题是哪些，问题如何解决 )。 1、普通背包问题： (1)输入物品个数n=3 (2)输入背包容量C：10

(3)输入各物品的大小或重量：6 、 5 、 5 (4)输入各物品的价值p：56 、 23 、 43

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法设计_课程设计在线全文阅读。