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

课 程 设 计 报 告

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

系 : 三系

学生姓名： 吴 阳

班 级： 12软件（2)班

学 号： 20120311232

成 绩：

指导教师： 秦川

开课时间： 2014 学年 一 学期

一、问题描述

1．普通背包问题

给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi，背包的容量为C。选择装入的背包的物品，使得装入背包中的物品的总价值最大，在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

2．0/1背包问题

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi,背包的容量为C。选择装入的背包的物品，使得装入背包中的物品的总价值最大,在选择物品i装入背包时，对于每种物品i只有两种选择，即装入背包或者不装入背包，不能将物品装入背包多次,也不能只装入部分的物品i。

3．棋盘覆盖问题

在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌(每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。

二、问题分析

1．普通背包问题

对于背包问题，若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量Ｗ，剩余的将是n-1个原重物品1,2，······,j-1，j+1，·····，n以及重为Ｗi－Ｗ的物品j中可装入容量为C－Ｗ的背包且具有最大价值的物品。

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个物品已经确定的情况下）,我们可以考虑我们能够达到的最大的价值，即我们可以通过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。通过该条件，可以减去很多的枝条，大大节省运行时间。

3．棋盘覆盖问题

每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角方格的行列坐标,然后再与特殊方格坐标进行比较，就可以知道特殊方格是否在该块中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。在递归函数里，还要有一个变量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,使得niwixi1≤C,而且nxi1ivi达到最大.

2．0/1背包问题

0-1背包问题的数学描述为：不能将物品装入背包多次,也不能只装入部分的物品i. C〉0,wi〉0,vi〉0，1≤i≤n，要求找出一个n元0-1向量（x1，x2，x3,·····，xn）,xi∈｛0,1},1≤i≤n，使得niwixi1≤C，而且nxi1ivi达到最大。

3．棋盘覆盖问题

当k〉0时，将2k×2k棋盘分割为4个2^k-1×2^k-1 子棋盘（a）所示.特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如 （b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题.递归地使用这种分割，直至棋盘简化为棋盘1×1.

四、算法设计

1．普通背包问题

因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优,可以用贪心法解决。

算法设计：首先计算每种物品单位重量的价值Vi/Wi，然后按单位重量价值从大到小进行排序,根据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包.或将这种物品全部装入背包后，背包内的物品总重量未超过背包容量C，则选择单位重量价值次高的物品并尽可能多地装入背包，依此策略一直进行下去,直到背包装满为止。

2．0/1背包问题

该0—1背包问题采用的是回溯算法,回溯算法的基本解题步骤是:

（1）针对所给问题定义问题的解空间;

（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效的搜索。

算法设计:

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．棋盘覆盖问题

该棋盘算法用的是分治算法，分治法解题的思路就是将大问题化为若干子问题,再依次解决子问题,最后获得问题的答案。

算法设计：

（1）ChessBoard函数实现了递归的将棋盘划分为子棋盘，并将棋盘进行覆盖。

（2) main(）函数用来进行输入棋盘的大小和特殊棋盘的位置。

（3）使用memset（Matrix,0，sizeof(Matrix)）将Matrix［]数组清零.

五、算法实现

1．普通背包问题

＃include 〈stdio。h>

struct goodinfo

｛

float p；//物品价值

float w；//物品重量

float x;//物品该放数量

int flag;//物品编码

｝;

void Insertionsort(goodinfo goods［］，int n)

｛

int i,j;

for (j=2;j<=n；j++）

｛

goods[0]=goods[j];

i=j-1;

while （goods［0].p >goods[i］。p )

{

goods[i+1]=goods[i];

i-—;

}

goods[i+1]=goods[0];

｝

}

//按物品效益重量比值做降序排列

void bag(goodinfo goods[］，float M,int n)

｛

float cu;

int i,j;

for(i=1；i〈=n;i++）

goods［i]。x=0;

cu=M;

for（i=1;i<=n；i++)

{

if（goods［i］。w>cu)

break； //当物品重量大于剩余容量时跳出

goods［i］.x =1;

cu=cu-goods[i]。w ；//确定背包新的剩余容量

}

if（i〈=n）

{

goods［i］.x =cu/goods[i］.w ;//该物品所要放的量

｝

//按物品编号做降序排列

for（j=2；j〈=n;j++）

｛

goods［0]=goods[j];

i=j-1；

while （goods[0].flag

｛

goods[i+1］=goods[i]；

i--；

}

goods［i+1]=goods［0];

}

printf（"最优解为：\n");

for(i=1;i〈=n；i++)

{