[算法学习笔记][刷题笔记] 2023/8/26&8/27 解题报告状压 dp
题单
状压 dp
状压 dp是一种非常暴力的算法，它直接记录不同的状态，通过状态进行转移。
状压 dp可以解决 NP 类问题。它的原理是暴力枚举每一种可能的状态。所以它的复杂度是指数级的。只能求解小范围的问题。
关于记录状态：
状压 dp 通过一个二进制串来记录状态。显然二进制串可以转换成十进制在数组中作为下标。这也是它优化状态的关键。同时，二进制串可以直接通过 位运算 转移状态。
一般来讲思考状压 dp 的步骤是先判断有无后效性，即可否用朴素的 dp 例如线性 dp 解决。如果有后效性，考虑记录完整状态，也就是状压 dp。
接下来将通过一些例题来进一步理解状压 dp。
[USACO12 MAR Cows in a Skyscraper G]
给出 \(n\) 个物品，体积为 \(w_i\)，现把其分成若干组，要求每组总体积\(\leq W\)，问最小分组。\(n\leq 18\)
Solution
类似于 01 背包，每个物品只能分到一个组中，即后面的状态不能包含前面的状态。有后效性。无法使用朴素线性 dp 解决。
数据范围 \(n\leq 18\)。可以用指数级的算法。
定义 \(f_{i,j}\) 表示分成了 \(i\) 组，且状态为 \(j\) 时的最小体积。
关于状态：我们把状态设计为二进制串，例如 \(00110\) 表示只有第 \(3,4\) 个物品被选择过，被包含在这一个状态内。
定义状态上界：每个物品都可以是 \(0,1\)。因此最多有 \(2^n\) 个状态。我们可以把每一个状态都枚举。因为此类问题有后效性，无法简化。
接下来枚举分成了多少组，显然最多分成 \(n\) 组。
对于每个分组数，我们都可能遇到每个可能状态，所以暴力枚举。
现在，对于分成当前组数，当前状态。我们需要对每个物品进行决策，也就是更新，所以再枚举每个物品。
对于每个物品，如果它被包含在该状态，或者当前分组，当前状态下最后一个分组的体积+当前物品体积超过上限。都不可以在当前状态下选择该物品。
反之，更新状态。若设当前分成了 \(i\) 组，状态为 \(x\)，当前是第 \(j\) 个物品，则更新：
\(f_{i,x|1<<j}=min(f_{i,x|1<<j,f_{i,x}+a_j})\)
对于必须将该物品单独分为一组，则：
\(f_{i+1,x|1<<j}=min(f_{i+1,x|1<<j},a_j)\)
Explanation：1<<j 表示新建一个二进制串，并且将 \(1\) 移动到第 \(k\) 位，也就是 \(2^k\) 。\(x|1<<j\) 也就使 \(x\) 状态的第 \(j\) 位变成 \(1\) 后的状态决策。
最后统计答案正着搜到第一个不是 INF 的组输出即可。
上述决策需要注意，必须在 \(f_{i,x}\) 被决策后才能继续。
初始化使得分成1组，状态为每个物品的体积都为它本身，具体实现见代码：
实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1000010;
const int INF = 0x3f3f3f3f;
int up;
int n,w;
int a[N];
int f[20][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>w;
for(int i=0;i<n;i++) cin>>a[i];
up = pow(2,n);
memset(f,INF,sizeof f);
for(int i=0;i<n;i++) f[1][1<<i] = a[i];
for(int i=0;i<=n;i++)
{
for(int j=0;j<up;j++)
{
if(f[i][j] != INF)
{
for(int k=0;k<n;k++)
{
if(j&(1<<k)) continue;
if(f[i][j]+a[k] <= w)
{
f[i][j|(1<<k)] = min(f[i][j|(1<<k)],f[i][j]+a[k]);
}
else
{
f[i+1][j|(1<<k)] = min(f[i][j|(1<<k)],a[k]);
}
}
}
}
}
for(int i=0;i<=n;i++)
{
if(f[i][up-1] != INF)
{
cout<<i<<endl;
return 0;
}
}
}
Luogu P1433 吃奶酪
房间里放着 \(n\) 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 \((0,0)\) 点处。
Solution
我们发现它的位置是必要的。我们只需要记录它最后一步是在哪里即可。
定义 \(f_{i,j}\) 表示状态为 \(i\) 的前提下，最后吃的是 \(j\) 最小需要跑多少。
首先 \(n^2\) 预处理任意两点的距离。
考虑枚举每一种状态，枚举最后吃的哪一个，显然如果枚举到最后吃的这个奶酪不包含在状态中则不处理。
否则，更新它。枚举它可以从哪个节点 \(k\) 转移过来。转移的前提同理是 \(k\) 被包含在这个状态。然后枚举先吃 \(k\)，然后再吃当前节点即可。
我们显然不希望重复吃，也就是不重复吃 \(j\)，因为我们当前更新的是最后吃 \(j\) 的情况下，具体地：
\(f_{i,j}=min(f_{i,j},f{i^(1<<(j-1)),k}+dist_{k,j})\)
实现
/*
状压dp
一般来说 f 数组中用二进制串来表示状态。一般解决“看似有后效性” 的问题。例如本题我们需要记录一个奶酪究竟有没有被吃。
记录完状态后考虑如何转移。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N =18 ;
int n;
double dist[N][N];
double x[N],y[N];
double f[1<<N][N];
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
for(int i=1;i<(1<<18);i++)
{
for(int j=0;j<18;j++){
f[i][j]=10000000.0;
}
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&x[i],&y[i]);
f[1<<(i-1)][i] = (double)sqrt(x[i]*x[i]+y[i]*y[i]);
// cout<<x[i]<<" "<<y[i]<<endl;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dist[i][j] = (double)sqrt((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
}
}
for(int i=1;i<(1<<n);i++) //最多有 2^n 种状态。
{
for(int j=1;j<=n;j++) //对于每一种状态进行枚举，以当前走到该节点的前提是本次状态和该节点一致
{
if(i&(1<<(j-1)) == 0) continue; //当前节点被包含在该状态时才可以继续
for(int k=1;k<=n;k++)
{
if(j == k) continue; //对于每一个节点考虑先吃 k在吃j
if((i&(1<<(k-1))) == 0) continue; //同理如果状态不包含则不能处理
f[i][j] = min(f[i][j],f[i^(1<<(j-1))][k]+dist[j][k]); //转移，我们不希望重复吃，所以先前的状态应与当前状态相反。
// cout<<f[i][j]<<endl;
}
}
}
double minn = 100000000.0;
for(int i=1;i<=n;i++) minn = min(minn,f[(1<<n)-1][i]); //状态确定，枚举以哪个节点为结尾。
printf("%.2lf\n",minn);
// cout<<minn<<endl;
return 0;
}