30基于状态压缩的动态规划
基于状态压缩的动态规划
一般，以集合信息为状态的特殊的动态规划问题。
首先满足动态规划的基本特点
其次数据规模较小
引入
信息的最小单位：bit（由0和1组成）
位运算：左移、右移
用0和1组成的数字对任意一个集合，对子集进行编码、掩码。
取第i位的值：S&（1<<i）
将第i位设置为1/0：S|（1<<i） S&~(1<<i）
例题
100顶帽子分给十个人
发布于
一般，以集合信息为状态的特殊的动态规划问题。
首先满足动态规划的基本特点
其次数据规模较小
信息的最小单位：bit（由0和1组成）
位运算：左移、右移
用0和1组成的数字对任意一个集合，对子集进行编码、掩码。
取第i位的值：S&（1<<i）
将第i位设置为1/0：S|（1<<i） S&~(1<<i）
100顶帽子分给十个人