算法分析与设计课程设计报告.docx
《算法分析与设计课程设计报告.docx》由会员分享，可在线阅读，更多相关《算法分析与设计课程设计报告.docx（35页珍藏版）》请在冰点文库上搜索。
算法分析与设计课程设计报告
一、问题描述
1、普通背包问题
有一个背包容量为C，输入N个物品，每个物品有重量S[i]，以及物品放入背包中所得的收益P[i]。
求选择放入的物品，不超过背包的容量，且得到的收益最好。
物品可以拆分，利用贪心算法解决。
2、0-1背包问题
在0/1背包问题中，需对容量为c的背包进行装载。
从n个物品中选取装入背包的物品，每件物品i的重量为wi,价值为pi。
对于可行的背包装载，背包中的物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，
即取得最大值。
约束条件<=c和。
在这个表达式中，需求出xi的值。
xi=1表示物品i装入背包中，xi=0表示物品i不装入背包。
3、棋盘覆盖问题
在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
二、问题分析
1、普通背包问题
贪心算法的基本思想是：
从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。
当达到算法中的某一步不能再继续前进时，算法停止。
背包问题用贪心算法来解决，先求出每件物品的平均价值即p[i]/s[i]，然后每次选择利润p[i]/s[i]最大的物品装进背包，这样就使得目标函数增加最快，当最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。
2、0-1背包问题
回溯法：
是一个既带有系统性又带有跳跃性的的搜索算法。
其基本思想是在搜索尝试中找问题的解，当不满足条件就”回溯”返回，尝试别的路径。
它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其原先结点回溯。
否则，进入该子树，继续按深度优先的策略进行搜索。
利用回溯算法来解决0-1背包，首先是将可供选择的物品的个数输入程序，将物品排成一列，计算总物品的重量weight，然后输入背包的实际重量weight，如果背包的重量小于0或者大于物品的总重量weight，则判断输入的背包重量错误，否则开始顺序选取物品装入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品"太大"不能装入，则弃之而继续选取下一件，直至背包装满为止。
但如果在剩余的物品中找不到合适的物品以填满背包，则说明"刚刚"装入背包的那件物品"不合适"，应将它取出"弃之一边"，继续再从"它之后"的物品中选取，如此重复，直至求得满足条件的解。
因为回溯求解的规则是"后进先出"，所以要用到栈来存储符合条件的解，在存储过程中，利用数组来存储各个物品的体积，然后用深度优先的搜索方式求解，将符合条件的数组元素的下标存入栈里，最后得到符合条件的解并且实现输出。
3、棋盘覆盖问题
将2^kx2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。
如果是：
左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格；
右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格；
左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格；
右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格。
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。
这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
三、算法设计
1、普通背包问题
1）基本思路：
首先，按物品单位价值由大到小将物品排序；（为了贪心选择准备）
然后，依次将单位价值大的物品放入背包（贪心选择），直到背包放满为止；
在向背包放置物品的过程中，如果正在考虑装入的物品不能全部放进去，则可以将物品的部分放入背包；
2）算法设计：
用一维数组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
从以上例子还可以发现，当残缺方格在第1个子棋盘，用①号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图4-9所示），当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。
如下图4.4所示：
图4.4
2）棋盘的识别：
棋盘的规模是一个必要的信息，有了这个信息，只要知道其左上角的左上角方格所在行、列就可以唯一确定一个棋盘了，残缺方格或“伪”残缺方格直接用行、列号记录。
•tr棋盘中左上角方格所在行。
•tc棋盘中左上角方格所在列。
•dr残缺方块所在行。
•dl残缺方块所在列。
•size:
棋盘的行数或列数
3）数据结构设计：
用二维数组board[][]，模拟棋盘。
覆盖残缺棋盘所需要的三格板（L牌）数目为：
（size2-1）/3；将这些三格板编号为1到（size2-1）/3。
则将残缺棋盘三格板编号的存储在数组board[][]的对应位置中，这样输出数组内容就是问题的解。
结合图4.4，理解算法。
四、算法实现
1、普通背包问题
1）声明变量、函数
//声明变量
intN;//物品数量
intM;//背包容量
doubleX[MAX];//背包问题最优解
doubleWeight[MAX];//物品重量
doublePrice[MAX];//物品价值
doubleunit_price[MAX];//物品单位价值
doubletotal_price;//背包总价值
//声明函数
voidInput（）;//输入函数
voidMergesort（）;//排序
voidknapsack（）;//背包装载
intOutput（）;//结果输出。
2）实现了按照价值密度的降序排列
voidMergesort（）
{
doubletemp1,temp2,temp3;
for（inti=1;i{
for（intj=1;j<=N-i;j++）
{
if（unit_price[j]{
temp1=Price[j];
Price[j]=Price[j+1];
Price[j+1]=temp1;
temp2=Weight[j];
Weight[j]=Weight[j+1];
Weight[j+1]=temp2;
temp3=unit_price[j];
unit_price[j]=unit_price[j+1];
unit_price[j+1]=temp3;
}
}
}
}
3）求最大总价值
voidknapsack（）
{
for（inti=1;i<=N;i++）//初始化X[i]，所有物品没有放入背包
{
unit_price[i]=Price[i]/Weight[i];//计算物品单位价值unit_price[]
X[i]=0;
}
doubleleft=M;//背包剩余载重
Mergesort（）;//按单位价值将物品排序，便于贪心选择
while（left!
=0）
{
for（inti=1;i<=N;i++）//贪心选择，总是选择价值最大放入背包
{
if（Weight[i]<=left）//当前物品小于背包剩余载重
{//整个放入背包
X[i]=1;
left=left-Weight[i];
total_price=total_price+Price[i];
}
elseif（Weight[i]>left）
{//部分放入背包
X[i]=left/Weight[i];
left=0;
total_price=total_price+Price[i]*X[i];
}
}
}
}
2、0-1背包问题
1）声明变量、函数
#defineN100//最大物品数
//声明变量
doublec;//背包容量
intn;//物品数
doublew[N];//物品重量数组
doublep[N];//物品价值数组
doublecw;//当前重量
doublecp;//当前价值
doublebestp;//当前最优价值
intpath[N];//当前最优路径
intx[N];//最佳装载
//声明结构体Goods
structGoods
{
doubleweight;//物品重量
doubleprice;//总价值
intid;//物品编号
floatunit_price;//物品单位价值
};
Goodsgoods[N]={{0,0,0,0}};
//声明函数
voidbacktract（inti）;//搜索解空间函数
doublebound（inti）;//界限函数
voidInput（）;//输入函数
voidOutput（）;//输出函数
2）搜索解空间函数
//=============================搜索解空间====================
voidbacktract（inti）
{
//到达叶节点
if（i>=n）//i表示深度（层），i>n搜索到叶子节点
{
bestp=cp;
for（intj=0;jx[j]=path[j];
return;
}
//搜索子树
if（cw+w[i]<=c）//当前物品放入背包不超载
{//进入左子树
cw+=w[i];
cp+=p[i];
path[i]=1;
backtract（i+1）;//继续向下深度搜索
cw-=w[i];
cp-=p[i];
}
//进入右子树
if（bound（i+1）>bestp）//当前的节点不合适时，跳到下一个结点
{
path[i]=0;
backtract（i+1）;
}
}
3）界限函数：
//======限界函数,计算当前价值与剩余价值和====================
doublebound（inti）
{
doublecleft=c-cw;//剩余容量
doublebound=cp;//当前物品价值
//以物品单位重量价值递减的顺序装入物品
while（i<=n&&w[i]<=cleft）//装载剩下的物品
{
cleft-=w[i];
bound+=p[i];
i++;
}//w[i]>cleft跳出循环，背包装满,物品部分装入背包
//装满背包
if（i<=n）
bound+=p[i]*cleft/w[i];
returnbound;//当前物品价值与剩余物品价值之和
}
3、棋盘覆盖问题
1）声明变量：
//声明变量
inttitle=1;//L型骨牌号
intboard[64][64];//二维数组board[][]，模拟棋盘
/*
tr棋盘中左上角方格所在行。
tc棋盘中左上角方格所在列。
dr残缺方块所在行。
dl残缺方块所在列。
size:
棋盘的行数或列数
*/
2）棋盘覆盖分治实现：
voidchessBoard（inttr,inttc,intdr,intdc,intsize）
{
ints,t;
if（size==1）return;//size:
棋盘行数
t=title++;//L型骨牌号
s=size/2;//分割棋盘
//覆盖左上角子棋盘
if（drchessBoard（tr,tc,dr,dc,s）;
else//此棋盘中无特殊方格
{
board[tr+s-1][tc+s-1]=t;//用t号L型骨牌覆盖右下角
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;//用t号L型骨牌覆盖左下角
chessBoard（tr,tc+s,tr+s-1,tc+s,s）;//覆盖其余方格
}
//覆盖左下角子棋盘
if（dr>=tr+s&&dcchessBoard（tr+s,tc,dr,dc,s）;
else//此棋盘中无特殊方格
{
board[tr+s][tc+s-1]=t;//用t号L型骨牌覆盖右上角
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;//用t号L型骨牌覆盖左上角
chessBoard（tr+s,tc+s,tr+s,tc+s,s）;//覆盖其余方格
}
}
五、测试分析
1、普通背包问题
1）、输入物品个数N=3,如图6.1所示。
图6.1输入物品数
2）、输入背包容量M：
10，如图6.2所示。
图6.2输入背包容量
3）、输入各物品的大小或重量weight：
6、5、5，如图6.3所示。
图6.3输入物品重量
4）、输入各物品的价值p：
42、25、30，如图6.4所示。
图6.4输入物品价值
5）、显示背包装载结果，如图6.5所示。
图6.5结果显示
2、0-1背包问题
1）、输入背包容量：
10,如图6.6所示。
图6.6输入背包容量
2）、输入物品个数：
3，如图6.7所示。
图6.7输入物品数量
3）、输入各物品重量：
6、5、5，如图6.8所示。
图6.8输入物品重量
4）、输入各物品的价值：
42、25、30，如图6.9所示。
图6.9输入物品价值
5）、显示背包装载结果，如图6.10所示。
图6.10结果显示
3、棋盘覆盖问题
1）、输入size：
8，如图6.11所示。
图6.11输入棋盘大小
2）、输入特殊方块的位置:
43，如图6.12所示。
图6.12输入特殊方格位置
3）显示棋盘覆盖结果，如图6.13所示。
图6.13结果显示
六、结论
三个算法，普通背包问题是用的贪心算法设计的，0-1背包问题是用回溯算法实现的，棋盘覆盖问题是用的分治法设计的。
在开始设计时对贪心算法和分治算法的思想很好理解，但是在设计算法时大概思路还是有的，但写完算法写代码是发现写不出来，原因就是算法设计的还不够细，后来上网查了些资料，分析了别人的算法，最终实现了现在的算法设计。
在最终完成的程序中：
贪心算法求普通背包问题，基本上已经实现了主要的功能；01背包问题也能实现主要功能，但一开始未使用到界限函数，后来才加上；在分治算法求棋盘覆盖问题时，也基本上实现了它的功能，但在输入时还有不足，需要人工输入2的指数幂，不够方便。
而且界面不够友好，不能实现单步覆盖。
不过，总的来说这次实践也是有一定收获的，至少对书中这三个算法的知识进行了巩固，自己更进一步地理解了这三个算法——
贪心算法：
从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解。
回溯法：
就是一种穷举搜索算法。
通俗地讲：
回溯法是一种“能进则进，进不了则换，换不了则退”的基本搜索方法。
在0-1背包问题中，为了提高搜索效率，避免一些无效的搜索，则需要用限界函数bound（）剪去得不到最优解的子树。
分治法：
分而治之。
即将一个难以直接解决的大问题小规模化，待解出子问题解之后，将子问题解合并为该问题解。
七、源程序
1、普通背包问题
#include
#defineMAX100//物品件数最大值
//声明变量
intN;//物品数量
intM;//背包容量
doubleX[MAX];//背包问题最优解
doubleWeight[MAX];//物品重量
doublePrice[MAX];//物品价值
doubleunit_price[MAX];//物品单位价值
doubletotal_price;//背包总价值
//声明函数
voidInput（）;//输入函数
voidMergesort（）;//排序
voidknapsack（）;//背包装载
intOutput（）;//结果输出
//================输入函数====================================
voidInput（）
{
inti;
cout<<"请输入物体数N:
";
cin>>N;
cout<cout<<"请输入背包总容量M:
";
cin>>M;
cout<cout<<"请输入各物体的大小或重量weight:
"<for（i=1;i<=N;i++）
cin>>Weight[i];
cout<<"请输入各物体的价值price:
"<for（i=1;i<=N;i++）
cin>>Price[i];
cout<}
//================按照价值密度的降序排列===================
voidMergesort（）
{
doubletemp1,temp2,temp3;
for（inti=1;i{
for（intj=1;j<=N-i;j++）
{
if（unit_price[j]{
temp1=Price[j];Price[j]=Price[j+1];Price[j+1]=temp1;
temp2=Weight[j];Weight[j]=Weight[j+1];Weight[j+1]=temp2;
temp3=unit_price[j];unit_price[j]=unit_price[j+1];unit_price[j+1]=temp3;
}
}
}
}
//===============实现背包装载================================
voidknapsack（）
{
for（inti=1;i<=N;i++）//初始化X[i]，所有物品没有放入背包
{
unit_price[i]=Price[i]/Weight[i];//计算物品单位价值unit_price[]
X[i]=0;
}
doubleleft=M;//背包剩余载重
Mergesort（）;//按单位价值将物品排序，便于贪心选择
while（left!
=0）
{
for（inti=1;i<=N;i++）//贪心选择，总是选择价值最大放入背包
{
if（Weight[i]<=left）//当前物品小于背包剩余载重
{//整个放入背包
X[i]=1;
left=left-Weight[i];
total_price=total_price+Price[i];
}
elseif（Weight[i]>left）
{//部分放入背包
X[i]=left/Weight[i];
left=0;
total_price=total_price+Price[i]*X[i];
}
}
}
}
//============结果输出======================================
intOutput（）
{
charch;
cout<<"贪心算法实现背包装载结果为:
"<for（inti=1;i<=N;i++）
{
cout<<"第"<"<"<<<"物体价值密度:
"<}
cout<cout<<"向量表示:
"<<"（";
for（i=1;i<=N;i++）//输出背包问题最优解
{
cout<}
cout<<"）"<cout<<"背包的最优装载值为：
"<cout<<"按Y或y继续操作，否则按任意键"<
升级会员 