首页 > 代码库 > 3.4 熟练掌握动态规划——状态压缩DP
3.4 熟练掌握动态规划——状态压缩DP
旅行商问题:
给定一个N节点组成的带权有向图的距离矩阵D(i,j)(INF--没有边),求从定点0出发,经过每个节点恰好一次再返回节点0,所经过的边的权值最小为多少?
范围:
2<=n<=15
dp[k][status]——到达k节点时,已经走过的点的集合为status的最佳答案,status是一个二进制数字表示集合。
利用记忆化搜索的方法进行求解
//正确答案为DP(0,(1<<n)-1)int DP(int K,int Status)//到达节点K并且已经走过的节点集合为Status的最优值,节点从0开始(0...N-1){ if (dp[K][Status]!=INF) { return dp[K][Status]; } //枚举K可到的且存在于Status里的节点V for (int i=0;i<adj[k].size();i++) { edge &e = Edges[adj[k][i]]; int dist = e.dist; if ((Status<<e.to)&&1) { dp[K][Status]=min(dp[K][Status],dp[e.to][Status XOR (1<<e.to)]+dist); } } return dp[K][Status];}
3.4 熟练掌握动态规划——状态压缩DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。