算法设计课程设计

课程设计报告。

课程设计名称：算法设计与分析

系计算机科学系

学生姓名。班级。

学号。成绩。

指导教师：

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

一、问题描述。

1、普通背包装载问题。

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

-1背包装载问题。

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

3、棋盘覆盖问题。

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

二、问题分析。

1、普通背包装载问题：

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

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

-1背包装载问题：

回溯法的基本思想：通过系统地搜索一个问题的解空间来得到问题的解。为了实现回溯，首先需要针对所给问题定**空间。

这个解空间必须至少包含问题的一个解（可能是最优的），然后组织解空间，确定易于搜索的解空间结构后，按照深度优先策略从开始结点出发搜索解空间。并在搜索过程中利用约束函数在扩展结点处剪去不满足约束的子树，用目标函数剪去得不到最优解的子树，避免无效搜索。

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

求满足目标函数和约束方程的物品组合（x0，x1，x2，…，xn-1) 与相应的总价值v。

3、棋盘覆盖问题：

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

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

递归使用这种划分策略，直至将棋盘分割为1*1的子棋盘。

三、建立数学模型。

1、普通背包问题：

求平均价值即p[i]/s[i]

约束条件：c1<=0

-1背包装载问题：

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

求相应的总价值cw和总重量cp。

约束条件：目标函数和约束方程。

3、棋盘覆盖问题：

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个方格用同一个编号。

四、算法设计。

1、普通背包装载问题：

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

int n 物品个数double c 背包的容量。

double s[i] 物品的重量（或大小） double p[i]物品的价值。

void **erage(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])求物品总价值的函数。

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

-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=tc+s残缺棋盘位于右上棋盘。

chessboard(tr, tc+s, dr, dc, s);else

if(dr>=tr+s &&dc chessboard(tr+s, tc, dr, dc, s);else

if(dr>=tr+s &&dc>=tc+s残缺方格位于右下棋盘。

chessboard(tr+s, tc+s, dr, dc, s);else

五、测试分析。

测试数据，测试输出的结果；复杂度分析；每个模块设计和测试时存在问题的(问题是哪些，问题如何解决 )。

1、普通背包问题：

(1)输入物品个数n=3

(2)输入背包容量c：10

(3)输入各物品的大小或重量：6 、 5 、 5

(4)输入各物品的价值p：56 、 23 、 43

4)结果：该算法主要时间用于单位价值排序，起时间复杂度为o(n*logn);(折半插入排序时间)

贪心装载时，耗时主要用于与剩余载重比较(w[ i]<=mm)时间为o(n)；

故该算法的时间复杂度为：o(n*logn+n)；

记为： o(n*logn)；

-1背包装载问题：

1)输入背包最大容量c：10

2)输入物品个数n=3

3)输入物品的重量：6 、 5 、 5

4)输入各物品的价值p：56 、 23 、 43

5）结果。3、棋盘覆盖问题：

设t(k)是覆盖一个2k×2k棋盘所需时间；则其满足如下递归方程：

解此递归方程得： t(k)＝o(4k)，故该算法的时间复杂度为o(4k)

六、结论。1、普通背包问题采用贪心算法实现。

首先计算每种物品单位重量的价值表p[i]/s[i]，然后，依据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。这样就使得目标函数增加最快，当最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。

-1背包装载问题采用回溯算法实现。

设0/1背包问题的最优值为m( i, j )，即背包容量是j，可选择物品为i,i+1,…,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下：

m( i, j )=max

m(i+1,j)

m(n,j)=

算法设计课程设计

算法课程设计

算法课程设计

算法课程设计

其他用户还读了