算法设计普通背包问题与棋盘覆盖问题分析

1、目 录一、问题描述31、普通背包问题：32、棋盘覆盖问题：3二、问题分析31、普通背包问题：32、棋盘覆盖问题：4三、建立数学模型41、普通背包问题：4四、算法设计52、普通背包问题：52、棋盘覆盖问题：5五、算法实现61、普通背包问题：62、棋盘覆盖问题：9六、测试分析101、普通背包问题：102、棋盘覆盖问题：12七、结论13八、源程序131、普通背包问题：132、棋盘覆盖问题：16九、参考文献：17一、问题描述1、普通背包问题：有一个背包容量为C，输入N个物品，每个物品有重量Si，以及物品放入背包中所得的收益Pi。求选择放入的物品，不超过背包的容量，且得到的收益最好。物品可以拆分，利用贪

2、心算法解决。2、棋盘覆盖问题：在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。二、问题分析1、普通背包问题：贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。背包问题用贪心算法来解决，先求出每件物品的平均价值即pi/si，然后每次选择利润pi/si最大的物品装进背包，这样就使得目标函数增加最快，当最后一种物

3、品放不下时，选择一个适当的拆分，使物品装满背包，使得总的价值最大。2、棋盘覆盖问题：将2k x 2k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成

4、一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。三、建立数学模型（根据问题情况选择，不需要此步骤可不要）1、普通背包问题：求平均价值即pi/si约束条件：c1<=0四、算法设计2、普通背包问题：用贪心算法进行设计，贪心算法的基本思想是：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。int n 物品个数 double C 背包的容量double sM 物品的重量（或大小） double pM物品的价值void average(int n,double sM

5、,double pM)/按照价值密度的降序排列函数；double c1 背包剩余容量 totalp 物品的总价值void bag(int n,double C,double sM,double pM,double xM)求物品总价值的函数在求物品总价值函数中药调用average函数，在主函数中调用bag()函数。2、棋盘覆盖问题：采用分治法设计，分治法的基本思想：分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。将

6、2k x 2k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：左上的子棋盘（若不存在特殊方格）则将该子棋盘右下角的那个方格假设为特殊方格右上的子棋盘（若不存在特殊方格）则将该子棋盘左下角的那个方格假设为特殊方格左下的子棋盘（若不存在特殊方格）则将该子棋盘右上角的那个方格假设为特殊方格右下的子棋盘（若不存在特殊方格）则将该子棋盘左上角的那个方格假设为特殊方格当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，

7、我们就可以用递归算法解决。tr: 棋盘左上方格行号；tc：棋盘左上方格列号；dr：特殊方格所在行号；dc：特殊方格所在列号；size：棋盘规格2k×2k五、算法实现1、普通背包问题：（1）实现了按照价值密度的降序排列：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;i<n;i+) for(j=1;j<=n-i;j+) if(cj<cj+1) temp1=pj;pj=pj+1;pj+1=

8、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(si<=c1) xi=1; c1=c1-si; else if(si>c1) xi=c1/si; c1=0;/ totalp=totalp+pi*xi; ;（3）主函数：vo

9、id 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<<" 物体价值密

10、度:"<< pi/si<<" "<<endl; cout<<endl; cout<<"向量表示:"<<" ( " for(i=1;i<=n;i+) cout<<xi<<" " totalp=totalp+pi*xi; cout<<")"<<endl; cout<<"背包的总价值为："<<totalp<<en

11、dl; /背包所装载总价值 cout<<"按Y或y继续操作，否则按任意键"<<endl; cin>>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; cout<<"请输入物体数n:" cin>>n; cout<<endl; cout&l

12、t;<"请输入背包总容量C:" cin>>C; cout<<endl; cout<<"请输入各物体的大小或重量:"<<endl; for(i=1;i<=n;i+) cin>>si; cout<<"请输入各物体的价值p:"<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<endl;2、棋盘覆盖问题：（1）棋盘覆盖分治实现：void chessBoard(int tr, int tc,

13、 int dr, int dc, int size)if(size=1)return;int t=tile+;int s=size/2;if(dr<tr+s && dc<tc+s)chessBoard(tr, tc, dr, dc, s);elseboardtr+s-1tc+s-1=t;chessBoard(tr, tc, tr+s-1, tc+s-1, s);if(dr<tr+s && dc>=tc+s)chessBoard(tr, tc+s, dr, dc, s);elseboardtr+s-1tc+s=t;chessBoard(tr

14、, tc+s, tr+s-1, tc+s, s);if(dr>=tr+s && dc<tc+s)chessBoard(tr+s, tc, dr, dc, s);elseboardtr+stc+s-1=t;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);elseboardtr+stc+s=t;chessBoard(tr+s, tc+s, tr+s, tc+s, s);（2）主函数：void main

15、() int size;cout<<"输入棋盘的size(大小必须是2的n次幂): "cin>>size;int index_x,index_y;cout<<"输入特殊方格位置的坐标: "cin>>index_x>>index_y;chessBoard(0,0,index_x,index_y,size);for(int i=0;i<size;i+)for(int j=0;j<size;j+)cout<<boardij<<" "cout<

16、;<endl; 六、测试分析1、普通背包问题：（1）、输入物品个数n=3（2）、输入背包容量C：10（3）、输入各物品的大小或重量：6 、 5 、 5（4）、输入各物品的价值p：56 、 23 、 432、棋盘覆盖问题：（1）、输入size：8（2）、输入特殊方块的位置:1,1七、结论两个算法，普通背包问题是用的贪心算法设计的，棋盘覆盖问题是用的分治法设计的。在开始设计时对贪心算法和分治算法的思想很好理解，但是在设计算法时大概思路还是有的，但写完算法写代码是发现写不出来，原因就是算法设计的还不够细，后来上网查了些资料，分析了别人的算法，最终实现了现在的算法设计。在这两个算法中贪心算法求普

17、通背包问题，基本上已经实现了主要的功能，在分治算法求棋盘覆盖问题，也基本上实现了它的功能，但在输入时还有不足，需要人工输入2的指数幂，不够方便。不过总的来说这次实践收获很多，不仅对先前学到的知识进行了巩固，还在应用实践中获得了经验。八、源程序1、普通背包问题：#include<iostream.h> #define M 100 void display(int &n,double &C,double sM,double pM) int i; s0=0;p0=0; cout<<"请输入物体数n:" cin>>n; cout&

18、lt;<endl; cout<<"请输入背包总容量C:" cin>>C; cout<<endl; cout<<"请输入各物体的大小或重量:"<<endl; for(i=1;i<=n;i+) cin>>si; cout<<"请输入各物体的价值p:"<<endl; for(i=1;i<=n;i+) cin>>pi; cout<<endl;void average(int n,double sM,doub

19、le pM)/按照价值密度的降序排列； int i,j; double temp1,temp2,temp3,cM; for(i=1;i<=n;i+) ci=pi/si; for(i=1;i<n;i+) for(j=1;j<=n-i;j+) if(cj<cj+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; ;void bag(int n,double C,double sM,double pM,double xM)/totalp(总价值) i

20、nt i; double c1; average(n,s,p); c1=C; while(c1!=0) for(i=1;i<=n;i+) if(si<=c1) xi=1; c1=c1-si; else if(si>c1) 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); bag(n,C,s,p,x);/totalp cout<<"结果表示为:"

21、<<endl; for(i=1;i<=n;i+) cout<<"第"<<i<<"个物体大小:"<< si<<" 物体价值:"<< pi<<" 物体价值密度:"<< pi/si<<" "<<endl; cout<<endl; cout<<"向量表示:"<<" ( " for(i=1;i&

22、lt;=n;i+) cout<<xi<<" " totalp=totalp+pi*xi; cout<<")"<<endl; cout<<"背包的总价值为："<<totalp<<endl; /背包所装载总价值 cout<<"按Y或y继续操作，否则按任意键"<<endl; cin>>ch; if(ch='Y'|ch='y') continue; else break; 2、棋盘覆盖问题：#include<iostream.h>int tile=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(dr<tr+s && dc<tc+s)chessBoard(tr, tc, dr, dc, s);elseboardtr+s-1tc+s-1=t;chessBoard(tr, t