状态压缩类型动态规划.pptx
《状态压缩类型动态规划.pptx》由会员分享,可在线阅读,更多相关《状态压缩类型动态规划.pptx(23页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、广场铺砖问题给出一个W行H列的广场用1*2小砖铺盖,小砖之间互相不能重叠问有多少种不同的铺法?1=W,H=11第1页/共23页分析该题给出的广场的面积很小,给出了一种1*2的砖,问用砖去铺广场有多少种铺法?因为w,h=11,很容易想到采用搜索的方法,可以采用深搜或宽搜均可。尽管w,h=11,不很大,但是用1*2的砖铺,深度最大可达到11,这样,如果采用深搜,对于每一层都需要回溯,时间复杂度也很高。如果采用宽搜,每一个点都有2种铺法,因此可以扩展出2个结点,要求所有的解,必须扩展全部树结构,如果11层结点,是个完全二叉树,结点数量可达211*11=2121,无论空间和时间都难以承受。因此我们需要
2、采用其他方法。第2页/共23页进一步分析性质1:如果w和h都是奇数,则无解,否则有解。证明:w,h都是奇数,则w*h也是奇数,由于12的砖有2块,因此无论铺多少块都是偶数,因此不能覆盖所有的地板。如果地板的面积S是偶数,肯定能被2整除,因此可以用S/2块砖铺满整个地板。性质2:对于每铺一次地板,只会影响所铺的上下两行。证明:因为是12的砖铺,性质显然。性质3:如果按行铺地板,每一行的铺法都类似。证明:显然!第3页/共23页一个示例一个69的面积铺法如下图:可以看出,在按行铺的过程中,某些砖会分成两半,如图2,但最多也是向下突出一格,在图3中,我们将图2的空隙填满,则又转移到了下一种状态。第4页
3、/共23页状态的表示如果我们把行进行动态规划,则第i行的各种情况即表示第i个阶段的的各种状态。若某格被铺了砖,则用1表示,没有铺砖,则用0表示,那么行的状态就是一个w个格子的0,1串,即w位的二进制数。如下图状态为:100100下面就是由某个二进制数能转化到另一个二进制数的问题了。如下图,状态由100100 111100 和110100:第5页/共23页动态规划显然,对于每一行,宽度为w,每格可放0和1,因此有2w 种状态,如下图:设f(i,s)表示铺到第i行,状态为s的方案数,则初始值f(1,0)=1Ans=fh+10时间复杂度为O(h*2W)第6页/共23页基本位操作若当前状态为s,对s
4、有下列操作:判断第i位是否为0 (S&1 i)=0,意思是将1左移i位与s进行与运算后,看结果是否为0.将第i位置1 S|1 i,意思是将1左移动i位与s进行或运算.将第i位置0 S&(1 i),意思是s与第i位为0,其余位为1的数进行与运算。例如:s=1010101,i=5(S&1 i):1010101&0100000=0S|1 i:1010101|0100000=1110101S&(1 1如果前一行连续两个位置为0,那么这两个连续位置可以横放 即00-00如果前一行该位置为1,显然该位置不能再放,于是应该把该位置设置为0,即1-0第8页/共23页W=4,h=2的求解过程第9页/共23页vo
5、id dfs(int i,int s1,int s2,int d)if(s=m)/如第i行已经做完,则累加 fi+1s2+=fis1;else if(jj&(1 d)=0)/第d位为0 dfs(i,s1,s2|(1 d),d+1);/将第d位变为1,并右移1位 /如果第d+1位也为0,则直接搜索d+2位 if(s2 m-1&(jj&(1 (d+1)=0)dfs(i,s1,s2,d+2);else dfs(i,s1,s2&(1 d),d+1);/将第d位变为0,并右移1位 第10页/共23页硬木地板 有一MN 的矩形地板可以使用的地板砖形状有两种:1)21的矩形砖2)22中去掉一个11的角形砖你
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 状态 压缩 类型 动态 规划
限制150内