(算法设计课程设计.docVIP

课 程 设 计 报 告 课程设计名称：算法设计与分析 系 ： 计算机科学系 学生姓名： 班 级： 学 号： 成 绩： 指导教师： 开课时间： 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型骨牌不得重叠覆盖。 二、问题分析和约束方程的物品组合（x0，x1，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和总重量和约束方程 棋盘覆盖问题： (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个方格用同一个编号。 四、算法设计 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 若cpbestp，更新当前最优总价值为当前总价值（即bestp=cp），更新装载方案（即bestx[i]=x[i]( 1≤i≤n)）；② 采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）：1 x[i