本文主要是介绍旅行商问题之状压dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题背景
旅行商问题背景就是，给定点集S，如何从固定起点s出发，找到最短的环游路线，注意每个城市（除s外）只能进过一次。
POJ 3311 Hie with the Pie：http://poj.org/problem?id=3311
swust 411: 售货员的难题：http://acm.swust.edu.cn/#/problem/411/-1
解题思路
定义dp[state][i]为已经过的城市集合state和当前所在的城市i，（state不包括i）。
初始状态：dp[0][i] = g[0][i+1], i = 0, 1, 2, …, n
更新条件：dp[s_next][i] = dp[s][e] + g[e+1][i+1];
Note：注意POJ3311不是完全的旅行商问题，它不要求每个城市只经过一次。不过通过修改代码中的限制条件，可以将TSP解法松弛到这种情况。
实现代码
POJ 3311
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <alg这篇关于旅行商问题之状压dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
