dp和状态压缩dp的入门_不重不漏 子集

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

做题做到状态压缩dp真的看不懂答案了，从b站找了两个课听，受益匪浅，做了笔记。

---

一、DP入门

核心：从集合角度分析dp问题，经验也重要

有限级的最优化：从定义求：枚举太难

                DP优化：1.化零为整（状态表示fi）a：集合

                                                 b：属性（min，max，count）

1. 状态计算（化整为零）：先看一下fi表示的所有可能是什么：划分若干部分分别求。子集满足原则：不重不漏
2. 划分依据：找最后一个不同点

eg：01背包

1.分析

i代表对i件物体做决策，有两种方式—放入背包和不放入背包。
j表示当前背包剩余的容量。

分析：1.状态表示（每一维度）：集合：只考虑前i个物品，总体积不超过j的选法的集合                   属性：max    f（n，v）

            2.状态计算：选/不选第i个物品，分别取这俩的max

不选i：从1—i-1中选，且总体<=j     选：必然包含i（不变wi价值），f（i-1，j）。                       前面随便（变化部分f（i-1，j-vi）。

左右两边取max

空间优化：用滚动数组，只保留之前结果，从大到小循环。可以优化成一维。

2.代码

代码如下：

#include<iostream>
const int N=1010;
using namespace std;
int n,V;
int f[N][N];
int v[N],w[N];
 
int main(){
    cin>>n>>V;//n:一共有多少物品，v背包容量
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//背包第i个物品的容量和价值
    
    for(int i=1;i<=N;i++){
        for(int j=0;j<=V;j++){
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][V]<<endl;
    return 0;
    
    
}

二、状态压缩DP

1.概念

动态规划随着阶段增长，在每个状态维度上会不断扩展；任意时刻已求解状态和尚未求解的状态在各个维度上的分界点组成DP扩展的轮廓。对于某些问题，我们需要在动态规划的“状态”中记录一个集合，保存这个“轮廓”的详细信息，以便进行状态转移。 若集合大小不超过N，集合中每个元素都是小于K的自然数，则我们可以把这个集合看作一个N位K进制数，以一个[ O , K N − 1 ] [O,K^{N-1}][O,K N−1]之间的十进制整数的形式作为DP状态的一维。

状态压缩DP：将集合转化为整数记录在DP状态中的一类算法。

使用条件：一般能够采用状态压缩dp的题目数据规模都不大（<30），这是判断是否能够采用状态压缩dp的一个重要条件。（以上从别人博客引用）

2.前置技能

基础dp：背包，区间dp，树形dp

了解二进制运算符:<< >> | & ^

             

3.引入：经典tsp

找哈密顿回路 

二进制集合表示法：

1. 用一个数的二进制表示一个集合
2. 点的集合
3. 假设有个S=26=011010，每个二进制位是0：表示节点0不在s当中
4. 看出s表示的集合是{1 3 4}

状态表示

1. dp[i][s]表示当前在i节点，已经访问过节点集合为s，所经过路径的最小权值和。
2. 用s表示集合及所谓的状态压缩
3. Dp[1][26(10)]

为什么不记录路径：因为要减少状态，不用去记录走过的路

转移方程

1. 标号从0开始
2. dp[i][s|(1<<j)]=min(dp[i][s]+G[i][j]);i是当前所在节点，j是下一步要到达的节点，s是走过节点的集合
3. s|(1<<j):把s的第j个二进制位至1，把j这个元素加入s
4. G[i][j]是边i到j的边权，如果不通可以不进入转移方程
5. 边界状态：可以从任一点出发，dp[i][1<<i]=0表示从i出发

子集枚举

如何枚举这个集合？

1. dp[i][s|(1<<j)]=min(dp[i][s]+G[i][j])在s之后枚举就可以顺序正确
2. 所以就是从小到大枚举s：for(int s=0;s<(1<<n);++s)n代表有n个点，二进制有n位

4.核心代码

1.推以后

for(int s=0;s<(1<<n);++s)枚举s
for(int i=0;i<n;i++)if(s&(1<<i))//枚举i，如果i节点在集合中
    for(int j=0;j<n;j++)//枚举下一步要去的节点
       If(!(s&(1<<j))&&G[i][j])//如果j不在且有路径
           dp[j][s|(1<<i)]=min(dp[j][s|(1<<j)],dp[i][s]+G[i][j])

2.推之前

for(int s=0;s<(1<<n);++s)枚举s
for(int i=0;i<n;i++)if(s&(1<<i))//枚举i，如果i节点在集合中
    for(int j=0;j<n;j++)//枚举之前的节点
       If((s&(1<<j))&&G[j][i])//如果j在,且有路径
           dp[i][s]=min( dp[i][s],dp[j][s^(1<<i)]+G[j][i])

s^(1<<i)//按位异或

s的第i个二进制位肯定是1，在j那里第i位是0，因为还没访问呢，所以要把i去掉

---

总结

感谢b站的老师

一个是电子科大的，一个是闫老师讲的