目 录
一、问题描述 ................................................................................................................................... 2
1、普通背包问题： ................................................................................................................. 2 2、棋盘覆盖问题： ................................................................................................................. 2 二、问题分析 ................................................................................................................................... 2
1、普通背包问题： ................................................................................................................. 2 2、棋盘覆盖问题： ................................................................................................................. 3 三、建立数学模型 ........................................................................................................................... 3
1、普通背包问题： ................................................................................................................. 3 四、算法设计 ................................................................................................................................... 4
2、普通背包问题： ................................................................................................................. 4 2、棋盘覆盖问题： ................................................................................................................. 4 五、算法实现 ................................................................................................................................... 5
1、普通背包问题： ................................................................................................................. 5 2、棋盘覆盖问题： ................................................................................................................. 8 六、测试分析 ................................................................................................................................... 9
1、普通背包问题： ................................................................................................................. 9 2、棋盘覆盖问题： ............................................................................................................... 11 七、结论......................................................................................................................................... 12 八、源程序..................................................................................................................................... 12
1、普通背包问题： ............................................................................................................... 12 2、棋盘覆盖问题： ............................................................................................................... 15 九、参考文献： ............................................................................................................................. 16
一、问题描述
1、普通背包问题：
有一个背包容量为C，输入N个物品，每个物品有重量S[i]，以及物品放入背包中所得的收益P[i]。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪心算法解决。
2、棋盘覆盖问题：
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
二、问题分析
1、普通背包问题：
贪心算法的基本思想是：从问题的某一个初始解出发逐
步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。
背包问题用贪心算法来解决，先求出每件物品的平均价值即p[i]/s[i]，然后每次选择利润p[i]/s[i]最大的物品装进背包，这样就使得目标函数增加最快，当
2
最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。
2、棋盘覆盖问题：
将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
三、建立数学模型
（根据问题情况选择，不需要此步骤可不要）
1、普通背包问题：
求平均价值即p[i]/s[i] 约束条件： c1<=0
3
四、算法设计
2、普通背包问题：
用贪心算法进行设计，贪心算法的基本思想是：从问题的某一个初始解出发逐 步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。
int n 物品个数 double C 背包的容量
double s[M] 物品的重量（或大小） double p[M]物品的价值
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、棋盘覆盖问题：
采用分治法设计，分治法的基本思想：分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。
将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格
4
右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
tr: 棋盘左上方格行号； tc：棋盘左上方格列号； dr：特殊方格所在行号； dc：特殊方格所在列号； size：棋盘规格2k×2k
五、算法实现
1、普通背包问题：
（1）实现了按照价值密度的降序排列： void average(int n,double s[M],double p[M]) {int i,j;
double temp1,temp2,temp3,c[M]; for(i=1;i<=n;i++) c[i]=p[i]/s[i]; for(i=1;i { temp1=p[j];p[j]=p[j+1];p[j+1]=temp1; temp2=s[j];s[j]=s[j+1];s[j+1]=temp2; temp3=c[j];c[j]=c[j+1];c[j+1]=temp3; } }; 5
相关推荐：
loading