状态压缩的动态规划.doc

《状态压缩的动态规划.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于状态压缩的动态规划n名称：基于状态压缩的动态规划、集合动态规划。n含义：以一个集合内的元素信息作为状态，状态总数为指数级别的动态规划。n特点：1、本身要满足动态规划的性质：最优性原理、无后效性。2、数据中的某一维规模比较小。【预备知识】位运算基础知识 什么是位(bit)？   很简单，位(bit)就是单个的0或1，位是我们在计算机上所作一切的基础。计算机上的所有数据都是用位来存储的。一个字节(BYTE)由八个位组成，一个字(WORD)是二个字节或十六位，一个双字(DWORD)是二个字或三十二位。 使用位运算

2、的好处是可以将BYTE,  WORD  或  DWORD  作为小数组或结构使用。通过位运算可以检查位的值或赋值，也可以对整组的位进行运算。   16进制数及其与位的关系:   用0或1表示的数值就是二进制数，由于二进制表示起来很长，所以用16进制数。16进制数用4个位表示0  -  15的值，4个位组成一个16进制数。也把4位称为半字节(nibble)。一个BYTE有二个nibble，因此可以用二个16进制数表示一个BYTE。二进制与十六进制可以直接转换。如下所示：      NIBBLE      HEX 

3、    ======      =========     0000                0     0001                1     0010                2     0011                3     0100                4     0101                5     0110                6     0111                7     1000                

4、8     1001                9     1010                A     1011                B     1100                C     1101                D     1110                E     1111                F     如果用一个字节存放字母"r"(ASCII码114)，结果是：   0111  0010        ：二进制       7       

5、 2          ：16进制  可以表达为：'0x72'     有6种位运算：         &      与运算         

6、      或运算         ^      异或运算         ~      非运算(求补)       >>      右移运算       <<      左移运算  应用：【若当前状态为s，对s有下列操作】：1.判断第i位是否为0：(S&(1<

7、(1<

8、)，意思是将1左移i-1位与S进行或运算。3.将第i位置0：S&~(1<

9、1<

10、0100000=1110101S&~(1<

11、占用，就可以声明这样的结构：   struct  date_struct  {           BYTE      day      :  5,      //  1  to  31                         month  :  4,      //  1  to  12                         year    :  14;    //  0  to  9999           }date;   在结构中，日期数据占用最低5位，月份占用4位，年占用14位。这

12、样整个日期数据只需占用23位，即3个字节。忽略第24位。如果用整数来表达各个域，整个结构要占用12个字节。      

13、  0  0  0  0  0  0  0  0  

14、  0  0  0  0  0  0  0  0  

15、  0  0  0  0  0  0  0  0  

16、         

17、