算法设计普通背包问题与棋盘覆盖问题分析.docx
- 文档编号:1877005
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:15
- 大小:137.28KB
算法设计普通背包问题与棋盘覆盖问题分析.docx
《算法设计普通背包问题与棋盘覆盖问题分析.docx》由会员分享,可在线阅读,更多相关《算法设计普通背包问题与棋盘覆盖问题分析.docx(15页珍藏版)》请在冰点文库上搜索。
算法设计普通背包问题与棋盘覆盖问题分析
一、问题描述
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^kx2^k的棋盘,先分成相等的四块子棋盘,其中特殊方格位于四个中的一个,构造剩下没特殊方格三个子棋盘,将他们中的也假一个方格设为特殊方格。
如果是:
左上的子棋盘(若不存在特殊方格)则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘(若不存在特殊方格)则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘(若不存在特殊方格)则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘(若不存在特殊方格)则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种,只可能且必定只有三个成立,那三个假设的特殊方格刚好构成一个L型骨架,我们可以给它们作上相同的标记。
这样四个子棋盘就分别都和原来的大棋盘类似,我们就可以用递归算法解决。
三、建立数学模型
(根据问题情况选择,不需要此步骤可不要)
1、普通背包问题:
求平均价值即p[i]/s[i]
约束条件:
c1<=0
四、算法设计
2、普通背包问题:
用贪心算法进行设计,贪心算法的基本思想是:
从问题的某一个初始解出发逐
步逼近给定的目标,以尽可能快的求得更好的解。
当达到算法中的某一步不能再继续前进时,算法停止。
intn物品个数doubleC背包的容量
doubles[M]物品的重量(或大小)doublep[M]物品的价值
voidaverage(intn,doubles[M],doublep[M])//按照价值密度的降序排列函数;
doublec1背包剩余容量totalp物品的总价值
voidbag(intn,doubleC,doubles[M],doublep[M],doublex[M])求物品总价值的函数
在求物品总价值函数中药调用average函数,在主函数中调用bag()函数。
2、棋盘覆盖问题:
采用分治法设计,分治法的基本思想:
分治法求解问题的过程是,将整个问题分解成若干个小问题后分而治之。
如果分解得到的子问题相对来说还太大,则可反复使用分治策略将这些子问题分成更小的同类型子问题,直至产生出方便求解的子问题,必要时逐步合并这些子问题的解,从而得到问题的解。
将2^kx2^k的棋盘,先分成相等的四块子棋盘,其中特殊方格位于四个中的一个,构造剩下没特殊方格三个子棋盘,将他们中的也假一个方格设为特殊方格。
如果是:
左上的子棋盘(若不存在特殊方格)则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘(若不存在特殊方格)则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘(若不存在特殊方格)则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘(若不存在特殊方格)则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种,只可能且必定只有三个成立,那三个假设的特殊方格刚好构成一个L型骨架,我们可以给它们作上相同的标记。
这样四个子棋盘就分别都和原来的大棋盘类似,我们就可以用递归算法解决。
tr:
棋盘左上方格行号;
tc:
棋盘左上方格列号;
dr:
特殊方格所在行号;
dc:
特殊方格所在列号;
size:
棋盘规格2k×2k
五、算法实现
1、普通背包问题:
(1)实现了按照价值密度的降序排列:
voidaverage(intn,doubles[M],doublep[M])
{inti,j;
doubletemp1,temp2,temp3,c[M];
for(i=1;i<=n;i++)
c[i]=p[i]/s[i];
for(i=1;i for(j=1;j<=n-i;j++) if(c[j] {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; } }; (2)求最大总价值: voidbag(intn,doubleC,doubles[M],doublep[M],doublex[M]) {inti; doublec1; average(n,s,p); c1=C; while(c1! =0) {for(i=1;i<=n;i++) {if(s[i]<=c1) {x[i]=1; c1=c1-s[i];} elseif(s[i]>c1) {x[i]=c1/s[i]; c1=0;}//totalp=totalp+p[i]*x[i]; }}}; (3)主函数: voidmain() {inti,n; doubleC=0,totalp=0,s[M],p[M],x[M]; charch; while (1) {display(n,C,s,p); bag(n,C,s,p,x);//totalp cout<<"结果表示为: "< for(i=1;i<=n;i++) cout<<"第"< "< "< "< cout< cout<<"向量表示: "<<"("; for(i=1;i<=n;i++) {cout< totalp=totalp+p[i]*x[i];} cout<<")"< cout<<"背包的总价值为: "< cout<<"按Y或y继续操作,否则按任意键"< cin>>ch; if(ch=='Y'||ch=='y') continue; else break; }} 显示函数Display(): voiddisplay(int&n,double&C,doubles[M],doublep[M]) {inti;s[0]=0;p[0]=0; cout<<"请输入物体数n: "; cin>>n; cout< cout<<"请输入背包总容量C: "; cin>>C; cout< cout<<"请输入各物体的大小或重量: "< for(i=1;i<=n;i++) cin>>s[i]; cout<<"请输入各物体的价值p: "< for(i=1;i<=n;i++) cin>>p[i]; cout< }; 2、棋盘覆盖问题: (1)棋盘覆盖分治实现: voidchessBoard(inttr,inttc,intdr,intdc,intsize) {if(size==1) return; intt=tile++; ints=size/2; if(dr chessBoard(tr,tc,dr,dc,s); else {board[tr+s-1][tc+s-1]=t; chessBoard(tr,tc,tr+s-1,tc+s-1,s);} if(dr chessBoard(tr,tc+s,dr,dc,s); else {board[tr+s-1][tc+s]=t; chessBoard(tr,tc+s,tr+s-1,tc+s,s);} if(dr>=tr+s&&dc chessBoard(tr+s,tc,dr,dc,s); else {board[tr+s][tc+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); else {board[tr+s][tc+s]=t; chessBoard(tr+s,tc+s,tr+s,tc+s,s);} } (2)主函数: voidmain() {intsize; cout<<"输入棋盘的size(大小必须是2的n次幂): "; cin>>size; intindex_x,index_y; cout<<"输入特殊方格位置的坐标: "; cin>>index_x>>index_y; chessBoard(0,0,index_x,index_y,size); for(inti=0;i { for(intj=0;j cout< cout< } } 六、测试分析 1、普通背包问题: (1)、输入物品个数n=3 (2)、输入背包容量C: 10 (3)、输入各物品的大小或重量: 6、5、5 (4)、输入各物品的价值p: 56、23、43 2、棋盘覆盖问题: (1)、输入size: 8 (2)、输入特殊方块的位置: 1,1 七、结论 两个算法,普通背包问题是用的贪心算法设计的,棋盘覆盖问题是用的分治法设计的。 在开始设计时对贪心算法和分治算法的思想很好理解,但是在设计算法时大概思路还是有的,但写完算法写代码是发现写不出来,原因就是算法设计的还不够细,后来上网查了些资料,分析了别人的算法,最终实现了现在的算法设计。 在这两个算法中贪心算法求普通背包问题,基本上已经实现了主要的功能,在分治算法求棋盘覆盖问题,也基本上实现了它的功能,但在输入时还有不足,需要人工输入2的指数幂,不够方便。 不过总的来说这次实践收获很多,不仅对先前学到的知识进行了巩固,还在应用实践中获得了经验。 八、源程序 1、普通背包问题: #include #defineM100 voiddisplay(int&n,double&C,doubles[M],doublep[M]) {inti;s[0]=0;p[0]=0; cout<<"请输入物体数n: "; cin>>n; cout< cout<<"请输入背包总容量C: "; cin>>C; cout< cout<<"请输入各物体的大小或重量: "< for(i=1;i<=n;i++) cin>>s[i]; cout<<"请输入各物体的价值p: "< for(i=1;i<=n;i++) cin>>p[i]; cout< }; voidaverage(intn,doubles[M],doublep[M])//按照价值密度的降序排列; {inti,j; doubletemp1,temp2,temp3,c[M]; for(i=1;i<=n;i++) c[i]=p[i]/s[i]; for(i=1;i for(j=1;j<=n-i;j++) if(c[j] {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;}}; voidbag(intn,doubleC,doubles[M],doublep[M],doublex[M])//totalp(总价值) {inti;doublec1; average(n,s,p); c1=C; while(c1! =0) {for(i=1;i<=n;i++) {if(s[i]<=c1) {x[i]=1; c1=c1-s[i];} elseif(s[i]>c1) {x[i]=c1/s[i]; c1=0;}//totalp=totalp+p[i]*x[i]; }}}; voidmain() {inti,n; doubleC=0,totalp=0,s[M],p[M],x[M]; charch; while (1) {display(n,C,s,p); bag(n,C,s,p,x);//totalp cout<<"结果表示为: "< for(i=1;i<=n;i++) cout<<"第"< "< "< "< cout< cout<<"向量表示: "<<"("; for(i=1;i<=n;i++) {cout< totalp=totalp+p[i]*x[i];} cout<<")"< cout<<"背包的总价值为: "< cout<<"按Y或y继续操作,否则按任意键"< cin>>ch; if(ch=='Y'||ch=='y') continue; else break; } } 2、棋盘覆盖问题: #include inttile=1; intboard[100][100]; voidchessBoard(inttr,inttc,intdr,intdc,intsize) {if(size==1) return; intt=tile++; ints=size/2; if(dr chessBoard(tr,tc,dr,dc,s); else {board[tr+s-1][tc+s-1]=t; chessBoard(tr,tc,tr+s-1,tc+s-1,s);} if(dr chessBoard(tr,tc+s,dr,dc,s); else {board[tr+s-1][tc+s]=t; chessBoard(tr,tc+s,tr+s-1,tc+s,s);} if(dr>=tr+s&&dc chessBoard(tr+s,tc,dr,dc,s); else {board[tr+s][tc+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); else { board[tr+s][tc+s]=t; chessBoard(tr+s,tc+s,tr+s,tc+s,s);}} voidmain() { intsize; cout<<"输入棋盘的size(大小必须是2的n次幂): "; cin>>size; intindex_x,index_y; cout<<"输入特殊方格位置的坐标: "; cin>>index_x>>index_y; chessBoard(0,0,index_x,index_y,size); for(inti=0;i { for(intj=0;j cout< cout< } } 九、参考文献: 《算法设计与分析》第二版吕国英版清华大学出版社 如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。=tc+s) =tc+s)