DP专题七–有关复杂集合
最优配对问题
题目要求
空间里有n个点P0P1···Pn，你的任务是把他们配成n/2对（n是偶数）使得每个点恰好在一个点对中
所有点对中两点的距离之和应尽量小
分析
初始状态转移方程为：d(i,S)=min{|PiPj|+d(i-1,S-{i}-{j}} j属于S
但其实i并不需要保存 他已经隐含在S中了 S中的最大元素就是i
所有可以直接用d(s)表示把S中的元素两两配对的最小距离和
修改后的状态转移方程：d(S)=min{|PiPj|+d(S-{i}-{j}} j属于S i=S的最大值
所以本题的关键就是如何快速求出集合S的最大值
利用集合+位运算的相关知识可以达到平均判断次数为2
下面给出代码实现
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| using namespace std; double dp[1<<20]; int n,S; struct Node { int x,y,z; }node[20]; void init() { cin>>n; for(int i=0;i<n;i++) cin>>node[i].x>>node[i].y>>node[i].z; S=1<<n; dp[0]=0; //没有点初始化为0 } double dis(Node &a,Node &b) //计算两点间的距离（三维） { return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z)); } void solve() { for(int s=1;s<S;s++) //S表示n的集合 { int i,j; dp[s]=INT_MAX; for(i=n-1;i>=0;i--) //i是集合S的最大值 if(s&(1<<i)) //高位递减 只要进入集合S就退出 i即为最大值 break; for(j=i-1;j>=0;j--) //j比i小 递减 if(s&(1<<j)) //j需确保在集合S中 dp[s]=min(dp[s],dis(node[i],node[j])+dp[s^(1<<i)^(1<<j)]); } //状态转移方程 异或等价于删去集合中的元素i和j } int main() { freopen("input.txt","r",stdin); init(); solve(); printf("%.3lf\n",dp[S-1]); return 0; }
|
货郎担问题–TSP
题目要求
有n个城市 两两之间均有道路直接相连 给出每两个城市i和j之间的道路长度Lij 求一条经过每个城市一次且仅一次 最后回到起点的路线
使得经过的道路总长度最短 N≤15
分析
假定我们从城市1出发，经过了一些地方，并到达了城市j。毋庸置疑，我们需要记录的信息有当前的城市j。同时我们还需要记录已经走过的城市的集合。同理，
使用S记录未走过的城市的集合也可以的，且运算方便。
于是我们可以得出状态转移方程 go(S,init)=min{go(S−i,i)+dp[i][init]}∀s∈S go(s,init)表示从init点开始，要经过s集合中的所有点的距离
因为是NP问题，所以时间复杂度通常比较大。使用dis[s][init]用来去重，初始化为-1，如果已经计算过init—>S（递归形式），则直接返回即可
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| using namespace std; int s; int N;//点的个数 int init_point; double x[20]; double y[20]; double dp[20][20];//两个城市的距离 double dis[1048577][20];//2^20=1048576 表示出发点到S集合是否已经访问过 double go(int s,int init) { if(dis[s][init]!=-1) return dis[s][init];//去重 if(s==(1<<(N-1))) return dp[N-1][init];//只有最后一个点返回 double minlen=100000; for(int i=0;i<N-1;i++)//只能在1到n-2点中查找 { if(s&(1<<i))//如果i点在s中且不为发出点 { if(go(s&(~(1<<i)),i)+dp[i][init]<minlen) minlen=go(s&(~(1<<i)),i)+dp[i][init]; } } return dis[s][init]=minlen; } int main() { int T; cin>>T; while(T--)//测试样例数 { cin>>N; for(int i=0;i<N;i++) cin>>x[i]>>y[i];//读入城市的坐标 for(int i=0;i<N;i++) for(int j=0;j<N;j++) { dp[i][j]=sqrt(pow((x[i]-x[j]),2)+pow((y[i]-y[j]),2)); //计算两个城市的距离 } for(int i=0;i<pow(2,N);i++) for(int j=0;j<N;j++) dis[i][j]=-1;//去重数组初始化 init_point=0; s=0; for(int i=1;i<N;i++) s=s|(1<<i);//从1开始，保证初始点没有在S里面 double distance=go(s,init_point); cout<<fixed<<setprecision(2)<<distance<<endl; } }
|
图的色数
题目要求
给定一个无向图G 把图中的结点染成尽量少的颜色 使得相邻结点颜色不同
分析
设d(S)表示把结点集S染色 所需要颜色数的最小值 则d(S)=d(S-S’)+1 其中S’是S的子集 并且内部没有边
即不存在S’内的两个结点u和v使得u和v相邻 换句话说 S’是一个可以染成同一种颜色的结点集
