1、算法设计普通背包问题与棋盘覆盖问题分析一、问题描述1、普通背包问题：有一个背包容量为C，输入N个物品，每个物品有重量Si，以及物品放入背包中所得的收益Pi。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪心算法解决。2、棋盘覆盖问题：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。二、问题分析1、普通背包问题：贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可
2、能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。背包问题用贪心算法来解决，先求出每件物品的平均价值即pi/si，然后每次选择利润pi/si最大的物品装进背包，这样就使得目标函数增加最快，当最后一种物品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。2、棋盘覆盖问题：将2k x 2k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方
3、格左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。三、建立数学模型（根据问题情况选择，不需要此步骤可不要）1、普通背包问题：求平均价值即pi/si约束条件：c1=0四、算法设计2、普通背包问题：用贪心算法进行设计，贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的
4、某一步不能再继续前进时，算法停止。int n 物品个数 double C 背包的容量double sM 物品的重量（或大小） double pM物品的价值void average(int n,double sM,double pM)/按照价值密度的降序排列函数；double c1 背包剩余容量 totalp 物品的总价值void bag(int n,double C,double sM,double pM,double xM)求物品总价值的函数在求物品总价值函数中药调用average函数，在主函数中调用bag()函数。2、棋盘覆盖问题：采用分治法设计，分治法的基本思想：分治法求解问题的过程是，
5、将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。将2k x 2k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格右下的子棋盘（若不
6、存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。tr: 棋盘左上方格行号；tc：棋盘左上方格列号；dr：特殊方格所在行号；dc：特殊方格所在列号；size：棋盘规格2k2k五、算法实现1、普通背包问题：（1）实现了按照价值密度的降序排列：void average(int n,double sM,double pM) int i,j; double temp1,temp2,temp3,cM; for(i=1;i
7、=n;i+) ci=pi/si; for(i=1;in;i+) for(j=1;j=n-i;j+) if(cjcj+1) temp1=pj;pj=pj+1;pj+1=temp1; temp2=sj;sj=sj+1;sj+1=temp2; temp3=cj;cj=cj+1;cj+1=temp3; ;（2）求最大总价值：void bag(int n,double C,double sM,double pM,double xM) int i; double c1; average(n,s,p); c1=C; while(c1!=0) for(i=1;i=n;i+) if(sic1) xi=c1/si
8、; c1=0;/ totalp=totalp+pi*xi; ;（3）主函数：void main() int i,n; double C=0,totalp=0,sM,pM,xM; char ch; while(1) display(n,C,s,p); bag(n,C,s,p,x);/totalp cout结果表示为:endl; for(i=1;i=n;i+) cout第i个物体大小: si 物体价值: pi 物体价值密度: pi/si endl; coutendl; cout向量表示: ( ; for(i=1;i=n;i+) coutxi ; totalp=totalp+pi*xi; cout)
9、endl; cout背包的总价值为：totalpendl; /背包所装载总价值 cout按Y或y继续操作，否则按任意键ch; if(ch=Y|ch=y) continue; else break; 显示函数Display():void display(int &n,double &C,double sM,double pM)int i; s0=0; p0=0; coutn; coutendl; coutC; coutendl; cout请输入各物体的大小或重量:endl; for(i=1;isi; cout请输入各物体的价值p:endl; for(i=1;ipi; coutendl;2、棋盘覆
10、盖问题：（1）棋盘覆盖分治实现：void chessBoard(int tr, int tc, int dr, int dc, int size)if(size=1) return; int t=tile+; int s=size/2; if(drtr+s & dctc+s) chessBoard(tr, tc, dr, dc, s); else boardtr+s-1tc+s-1=t; chessBoard(tr, tc, tr+s-1, tc+s-1, s); if(dr=tc+s) chessBoard(tr, tc+s, dr, dc, s); else boardtr+s-1tc+s
11、=t; chessBoard(tr, tc+s, tr+s-1, tc+s, s); if(dr=tr+s & dc=tr+s & dc=tc+s) chessBoard(tr+s, tc+s, dr, dc, s); else boardtr+stc+s=t; chessBoard(tr+s, tc+s, tr+s, tc+s, s);（2）主函数：void main() int size; coutsize; int index_x,index_y; coutindex_xindex_y; chessBoard(0,0,index_x,index_y,size); for(int i=0;
12、isize;i+) for(int j=0;jsize;j+) coutboardij ; coutendl; 六、测试分析1、普通背包问题：（1）、输入物品个数n=3（2）、输入背包容量C：10（3）、输入各物品的大小或重量：6 、 5 、 5（4）、输入各物品的价值p：56 、 23 、 432、棋盘覆盖问题：（1）、输入size：8（2）、输入特殊方块的位置:1,1七、结论两个算法，普通背包问题是用的贪心算法设计的，棋盘覆盖问题是用的分治法设计的。在开始设计时对贪心算法和分治算法的思想很好理解，但是在设计算法时大概思路还是有的，但写完算法写代码是发现写不出来，原因就是算法设计的还不够细，
13、后来上网查了些资料，分析了别人的算法，最终实现了现在的算法设计。在这两个算法中贪心算法求普通背包问题，基本上已经实现了主要的功能，在分治算法求棋盘覆盖问题，也基本上实现了它的功能，但在输入时还有不足，需要人工输入2的指数幂，不够方便。不过总的来说这次实践收获很多，不仅对先前学到的知识进行了巩固，还在应用实践中获得了经验。八、源程序1、普通背包问题：#include #define M 100 void display(int &n,double &C,double sM,double pM) int i; s0=0;p0=0; coutn; coutendl; coutC; coutendl;
14、 cout请输入各物体的大小或重量:endl; for(i=1;isi; cout请输入各物体的价值p:endl; for(i=1;ipi; coutendl;void average(int n,double sM,double pM)/按照价值密度的降序排列； int i,j; double temp1,temp2,temp3,cM; for(i=1;i=n;i+) ci=pi/si; for(i=1;in;i+) for(j=1;j=n-i;j+) if(cjcj+1) temp1=pj;pj=pj+1;pj+1=temp1; temp2=sj;sj=sj+1;sj+1=temp2; t
15、emp3=cj;cj=cj+1;cj+1=temp3; ;void bag(int n,double C,double sM,double pM,double xM)/totalp(总价值) int i; double c1; average(n,s,p); c1=C; while(c1!=0) for(i=1;i=n;i+) if(sic1) xi=c1/si; c1=0; / totalp=totalp+pi*xi; ;void main() int i,n; double C=0,totalp=0,sM,pM,xM; char ch; while(1) display(n,C,s,p);
16、 bag(n,C,s,p,x);/totalp cout结果表示为:endl; for(i=1;i=n;i+) cout第i个物体大小: si 物体价值: pi 物体价值密度: pi/si endl; coutendl; cout向量表示: ( ; for(i=1;i=n;i+) coutxi ; totalp=totalp+pi*xi; cout)endl; cout背包的总价值为：totalpendl; /背包所装载总价值 cout按Y或y继续操作，否则按任意键ch; if(ch=Y|ch=y) continue; else break; 2、棋盘覆盖问题：#includeint tile
17、=1;int board100100;void chessBoard(int tr, int tc, int dr, int dc, int size) if(size=1) return; int t=tile+; int s=size/2; if(drtr+s & dctc+s) chessBoard(tr, tc, dr, dc, s); else boardtr+s-1tc+s-1=t; chessBoard(tr, tc, tr+s-1, tc+s-1, s); if(dr=tc+s) chessBoard(tr, tc+s, dr, dc, s); else boardtr+s-1
18、tc+s=t; chessBoard(tr, tc+s, tr+s-1, tc+s, s); if(dr=tr+s & dc=tr+s & dc=tc+s) chessBoard(tr+s, tc+s, dr, dc, s); else boardtr+stc+s=t; chessBoard(tr+s, tc+s, tr+s, tc+s, s);void main() int size; coutsize; int index_x,index_y; coutindex_xindex_y; chessBoard(0,0,index_x,index_y,size); for(int i=0;isize;i+) for(int j=0;jsize;j+) coutboardijt ; coutendl; 九、参考文献：算法设计与分析第二版 吕国英版 清华大学出版社
