课 程 设 计 报 告
课程设计名称： 算法设计与分析
系 别： 三 系
学生姓名： 孙 磊
班 级： 09软件（1）班
学 号： [1**********]
成 绩：
指导教师： 秦 川
开课时间： 2011-2012 学年 第一学期
目 录
一、问题描述„„„„„„„„„„„„„„„„„„„„„„„3
1.普通背包问题„„„„„„„„„„„„„„„„„„„„„„3
2.棋盘覆盖问题„„„„„„„„„„„„„„„„„„„„„„3
二、问题分析„„„„„„„„„„„„„„„„„„„„„„„3
1.普通背包„„„„„„„„„„„„„„„„„„„„„„„„3
2.棋盘覆盖„„„„„„„„„„„„„„„„„„„„„„„„4
三、建立数学模型„„„„„„„„„„„„„„„„„„„„„4
1.普通背包„„„„„„„„„„„„„„„„„„„„„„„„4
2.棋盘覆盖„„„„„„„„„„„„„„„„„„„„„„„„5
四、算法设计„„„„„„„„„„„„„„„„„„„„„„„5
1.普通背包„„„„„„„„„„„„„„„„„„„„„„„„5
2.棋盘覆盖„„„„„„„„„„„„„„„„„„„„„„„„6
五、算法实现（源程序）„„„„„„„„„„„„„„„„„„7
1.普通背包„„„„„„„„„„„„„„„„„„„„„„„„7
2.棋盘覆盖„„„„„„„„„„„„„„„„„„„„„„„„9
六、测试分析„„„„„„„„„„„„„„„„„„„„„„„11
1.普通背包„„„„„„„„„„„„„„„„„„„„„„„11
2.棋盘覆盖„„„„„„„„„„„„„„„„„„„„„„„14
七、结论„„„„„„„„„„„„„„„„„„„„„„„„16
八、参考文献„„„„„„„„„„„„„„„„„„„„„„„17
一、问题描述
1.普通背包问题 :
给定n种物品和一个背包。物品i的重量是wi，其价值是vi，背包的容量是C。应如何选择装入背包的物品，是得装入背包中的物品的总价值最大？在选择装入背包的物品是，对每种物品i的选择可以是物品的的一部分（即可以不是整数），而不一定要全部装入背包，1
2.棋盘覆盖问题：
在一个(2^k) × (2^k) 个 方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4^k情形，因而有4^k种不同的棋盘。图a所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图b所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊棋盘方格以外的所有方格，且任何两个L型骨牌不得重叠覆盖。
二、问题分析
1.普通背包：
贪心算法的基本思路：
从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策，尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法停止。 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
2.棋盘覆盖：
分析方法：
分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格(这句话很重要)，从而将原问题分解为规模较小的棋盘覆盖问题。先把原始棋盘划分成4个相等的棋盘，由于棋盘只有一个特殊棋盘，所以这4个子棋盘中只有一个子棋盘包含该特殊棋盘，以便采用递归的方法求解，可以用1一个L型骨牌覆盖这3个较小棋盘的汇合处（要理解这句话），如图(c)所示。从而将原问题转换为4个较小规模的棋盘覆盖问题。递归使用这种划分策略，直至将棋盘分割为1*1的子棋盘。
三、建立数学模型
1.普通背包：
//=========确定背包新的剩余容量============
left=left-goods[i].w;
//=========该物品所要放的量=========
goods[i].X=left/goods[i].w;
2.棋盘覆盖：
数据结构设计：
（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.普通背包：
// 先按物品效益，重量比值做升序排列
================================
void Insertionsort(Good goods[],int n)
{
int i,j;
for(j=2;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(Good goods[],float M,int n)
{ 。。。
left=M; //========背包剩余容量
{ 。。。 //========当该物品重量大与剩余容量跳出 。。。 //=========确定背包新的剩余容量 }
if(i
goods[i].X=left/goods[i].w;//=========该物品所要放的量
for(j=2;j
}
。。。
}
}
2.棋盘覆盖：
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
。。。
if(dr