算法课程设计.doc

课 程 设 计 报 告

课程设计名称： 算法设计与分析
系 别 ： 三 系
学 生 姓 名： 张 乐 乐
班 级： 软 件 工 程
学 号： 20090307110
成 绩：
指 导 教 师： 秦 川
开课时间： 2011 学年 1 学期

一、问题描述
描述要解决的问题
1. 普通背包问题。
背包载重：M＝10
物品重量：w1＝6、w2＝5、w3＝5
物品价值：p1＝42、p2＝25、p3＝30
2. 棋盘覆盖问题。
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

二、 问题分析
1.普通背包问题： ①按单位价值排序：A,B,C
②依次将单位价值大的装入：
装C： M余=10-3=7；
装B： M余=7-2=5；
装C： M余=5-5=0；
2.棋盘覆盖问题：当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(所示。
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。
递归地使用这种分割，直至棋盘简化为棋盘1×1。a)

三、 建立数学模型（根据问题情况选择，不需要此步骤可不要）
1. 普通背包问题。

2.棋盘覆盖问题
用二维数组board[ ][ ]，模拟棋盘。覆盖残缺棋盘所需要的三格板数目为：( size2 -1 ) / 3将这些三格板编号为1到( s i z e2-1 ) / 3。则将残缺棋盘三格板编号的存储在数组board[ ][ ]的对应位置中，这样输出数组内容就是问题的解。
四、 算法设计
1.普通背包问题：该算法主要时间用于单位价值排序，起时间复杂度为O(n*logn);(折半插入排序时间)
贪心装载时，耗时主要用于与剩余载重比较(w[ i]<=mm)时间为O(n)；
故该算法的时间复杂度为：O(n*logn+n)；
记为： O(n*logn)；

2.棋盘覆盖问题。
以k=2时的问题为例，用二分法进行分解，得到的是如下图，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当如图中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个①号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如右图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。

从以上例子还可以发现，当残缺方格在第1个子棋盘，用①号三格板覆盖其余三个子棋盘的交界方格，可以使另外三个子棋盘转化为独立子问题；同样地（如下图所示），当残缺方格在第2个子棋盘时，则首先用②号三格板进行棋盘覆盖，当残缺方格在第3个子棋盘时，则首先用③号三格板进行棋盘覆盖，当残缺方格在第4个子棋盘时，则首先用④号三格板进行棋盘覆盖，这样就使另外三个子棋盘转化为独立子问题。

五、 算法实现
1.普通背包问题。
float greedy_knapsack ( float M, float w[ ], float p[ ], float x[ ] )
// x[ ]背包问题最优解, w[ ]物品重量， P[ ]物品价值
{ int n=w.length;
float pp=0;
float mm＝M; //pp计算当前总价值，mm背包剩余载重
for( int i=1;i<=n; i++ )
{ float ww[ i]= p[ i] / w[ i]； //计算物品单位价值ww[ ]
x[ i]=0; } //初始化
Mergesort ( w[ ], n ); //按单位价值将物品排序，便于贪心选择
for( int i=1; i<=n; i++ ) //贪心选择，总是选择价值最大放入背包
{ if ( w[ i]<=mm ) //当前物品小于背包剩余载重
{ x[ i]=1; mm=mm - w[ i]; pp=pp + p[ i]; }
else { x[ i]=mm/w[ i]; pp=pp +mm*w[ i]; break; } //i部分放入背包
}
return pp;
}
2.棋盘覆盖问题。
void chessboard(int tr,int tc,int dr,int dc,int size)
{
if(size==1)return;//2*2
int s;
int t=tile_num++;//L型骨牌号 static int tile_num = 1;
s=size/2;//分割棋盘
if(dr<tr+s&&dc<tc+s)//覆盖左上角子棋盘
{
chessboard(tr,tc,dr,dc,s);//特殊方格在此棋盘中
}
else{//此棋盘中无特殊方格
{
board[tr+s-1][tc+s-1]=t;//用L型骨架覆盖右下角
chessboard(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余方格
}
if(dr<tr+s&&dc>=tc+s)//覆盖右上角子棋盘
chessboard(tr,tc+s,dr,dc,s);//特殊方格在此棋盘中
else{//此棋盘中无特殊方格
board[tr+s-1][tc+s]=t;//L型骨牌覆盖左下角
chessboard(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余方格
}
if(dr>=tr+s&&dc<tc+s)//覆盖左下角子棋盘
{
chessboard(tr+s,tc,dr,dc,s);//特殊方格在此棋盘中
}
else{//此棋盘中无特殊方格
{
board[tr+s][tc+s-1]=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;//用L型骨架覆盖左上角
chessboard(tr+s,tc+s,tr+s,tc+s,s);//覆盖其余方格
}
六、 测试分析
1.普通背包问题。

该算法主要时间用于单位价值排序，起时间复杂度为O(n*logn);(折半插入排序时间)
贪心装载时，耗时主要用于与剩余载重比较(w[ i]<=mm)时间为O(n)；
故该算法的时间复杂度为：O(n*logn+n)；
记为： O(n*logn)；
2．棋盘覆盖问题。

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

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

七、结论
1. 普通背包问题：采用贪心算法的思想，贪心算法原理是通过局部最优来达到全局最优，采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的（在一定标准下），决策一旦做出，就不可再更改。
2. 棋盘覆盖问题：采用分治算法的思想，分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格(这句话很重要)，从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘，由于棋盘只有一个特殊棋盘，所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘，以便采用递归的方法求解，可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处（要理解这句话），如图(c)所示。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略，直至将棋盘分割为1*1的子棋盘。
八、源程序
1.普通背包问题。
#include"iostream"
#include<stdio.h>
using namespace std;
#define N 100
struct goods //定义商品类，每个商品有，商品名，重量，价值，是否装入背包等属性,
{ //并且有相应的设置属性，和获取属性的方法
char name;
float weight;
float value;
float inBackpack;
};
int goodsNum;//商品数量
float backpack_weight;//背包载重
float backpack_value=0;//背包总价值
goods goodsArray[N]; //商品数组
float good_value[N];//商品单位价值数组
bool input()//输入商品、背包相关信息
{
cout<<"输入背包载重：";
cin>>backpack_weight;
cout<<endl;
cout<<"输入商品数量N (0<N<=100)：";
cin>>goodsNum;
cout<<endl;
for(int i=0;i<goodsNum;i++)
{
cout<<"输入第"<<i+1<<"个商品的信息（商品名 重量 价值）：";
cin>>goodsArray[i].name;
cin>>goodsArray[i].weight;
cin>>goodsArray[i].value;
goodsArray[i].inBackpack=0;
}
return i==goodsNum?true:false;
}
bool init_good_value()//初始化商品单位价值数组
{
for(int i=0;i<goodsNum;i++)
{
good_value[i]=goodsArray[i].value/goodsArray[i].weight;
}
return i==goodsNum?true:false;
}
bool rank_good_value()//根据单位价值，对商品数组进行排序
{
float a;
goods gd;
for(int i=0;i<goodsNum;i++)
for(int j=i+1;j<goodsNum;j++)
{
if(good_value[i]<good_value[j])
{
a=good_value[j];
good_value[j]=good_value[i];
good_value[i]=a;
gd=goodsArray[j];
goodsArray[j]=goodsArray[i];
goodsArray[i]=gd;
}
}
return i==goodsNum?true:false;
}
void outRank()//输出排序后的物品顺序
{
cout<<"根据单位重量价值，由大到小，对物品排序:"<<endl;
for(int i=0;i<goodsNum;i++)
{
cout<<goodsArray[i].name<<'\t';
}
cout<<endl;
cout<<"**************************************************"<<endl;
}
bool putInBackpack()//将物品装入背包
{
bool c=false;
int back_surWeight=backpack_weight,i=0;
while(back_surWeight>0 && i<goodsNum){
if(back_surWeight>=goodsArray[i].weight)
{
goodsArray[i].inBackpack=goodsArray[i].weight;
back_surWeight-=goodsArray[i].weight;
backpack_value+=goodsArray[i].value;
}
else
{
goodsArray[i].inBackpack=back_surWeight;
backpack_value+=good_value[i]*back_surWeight;
back_surWeight=0;
}
i++;
}
if(back_surWeight==0||i==goodsNum)
c=true;
return c;
}
void output()//输出背包内物品
{
cout<<"***************** START ************************"<<endl;
cout<<"商品名"<<'\t'<<"重量"<<'\t'<<"价值"<<endl;
for(int i=0;i<goodsNum;i++)
{
if(goodsArray[i].inBackpack>0){
cout<<goodsArray[i].name<<'\t'<<goodsArray[i].inBackpack<<'\t'
<<goodsArray[i].inBackpack*good_value[i]<<endl;
}
}
cout<<"**************************************************"<<endl;
cout<<"背包总价值为："<<backpack_value<<endl;
cout<<"***************** END ************************"<<endl;
}
int main()
{
if(input())
{
cout<<"商品信息输入完成!"<<endl;
cout<<"**************************************************"<<endl;
if(init_good_value())
if(rank_good_value())
{
outRank();
if(putInBackpack())
{
cout<<"物品已装入背包!信息如下："<<endl;
output();
}
else
cout<<"物品装入背包失败!"<<endl;
}
else
cout<<"根据单位重量价值，由大到小，对物品排序失败!"<<endl;
else
cout<<"初始化商品单位价值数组失败!"<<endl;
}
else
cout<<"商品信息录入失败!"<<endl;
return 1;
}
2.棋盘覆盖问题。
#include<stdio.h>
#include"iostream"
#define SIZE 4
using namespace std;
int board[SIZE][SIZE];
int tile_num=1;
//tr,tc:棋盘左上角的行号和列号
//dr,dc:特殊方格的行号和列号
//size=2^k
void chessboard(int tr,int tc,int dr,int dc,int size)
{
if(size==1)return;//2*2
int s;
int t=tile_num++;//L型骨牌号 static int tile_num = 1;
s=size/2;//分割棋盘
if(dr<tr+s&&dc<tc+s)//覆盖左上角子棋盘
{
chessboard(tr,tc,dr,dc,s);//特殊方格在此棋盘中
}
else{//此棋盘中无特殊方格
{
board[tr+s-1][tc+s-1]=t;//用L型骨架覆盖右下角
chessboard(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余方格
}
if(dr<tr+s&&dc>=tc+s)//覆盖右上角子棋盘
chessboard(tr,tc+s,dr,dc,s);//特殊方格在此棋盘中
else{//此棋盘中无特殊方格
board[tr+s-1][tc+s]=t;//L型骨牌覆盖左下角
chessboard(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余方格
}
if(dr>=tr+s&&dc<tc+s)//覆盖左下角子棋盘
{
chessboard(tr+s,tc,dr,dc,s);//特殊方格在此棋盘中
}
else{//此棋盘中无特殊方格
{
board[tr+s][tc+s-1]=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;//用L型骨架覆盖左上角
chessboard(tr+s,tc+s,tr+s,tc+s,s);//覆盖其余方格
}
void output()//输出覆盖的棋盘
{
for(int tr = 0; tr < SIZE; tr++)
{
for(int tc = 0; tc < SIZE; tc++)
{
printf("%-4d", board[tr][tc]);
}
printf("\n");
}
}
int main()
{
int tr,tc;
cout<<"输入特殊方格的行列（tr tc）：";
cin>>tr>>tc;
board[tr-1][tc-1] = 0;
chessboard(0, 0, tr-1, tc-1, SIZE);
output();
return 1;
}
九、参考文献（6个）
《算法设计与分析》郑宗汉, 郑晓明编著，清华大学出版社，2005
《c++程序设计与分析》马瑞新 等编著/2007-03-01/大连理工大学出版社
《算法设计方法》吴哲辉　等编著/2008-10-01/机械工业出版社
《c++程序设计与分析》（美）维斯 著/2006-11-01/人民邮电出版社