博客

问题背景

旅行商问题背景就是，给定点集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