UVA10702 Travelling Salesman 题解

Miya555 · 2023-07-22 10:01:47 · 题解

UVA10702 Travelling Salesman 题解

题面：

有个旅行的商人，他每到一个的新城市，便卖掉所有东西再购买新东西，从而获得利润。从某城市 A 到某城市 B 有固定利润（B 到 A 的利润可能不同）。已知城市可以重复到达，从 S 点出发，经过 T 个城市，有 E 个城市能作为终点，求最大的利润。

先定义状态： dp [ i ][ j ] 为走过 i 个城市，在 j 结束时的最大利润；

此时我们可以进一步推出转移方程：

贴代码：

#include <bits/stdc++.h>
const int MINN = -0x3f;
//TSP旅行商问题
int w[101][101], end[101], dp[1001][101], x, C, S, E, T, tot;

int main() {
    while (~scanf("%d%d%d%d", &C, &S, &E, &T) && C + S + E + T) {

        for (int i = 1; i <= C; i++) {
            for (int j = 1; j <= C; j++) {
                scanf("%d", &w[i][j]);
            }
            end[i] = 0;
        }
        for (int i = 1; i <= E; ++ i) {
            scanf("%d", &x);
            end[x] = 1;
        }
        for (int i = 0; i <= T; ++ i) {
            for (int j = 1; j <= C; ++ j) {
                dp[i][j] = MINN;
            }
        }
        //记得预处理dp数组
        dp[0][S] = 0;
        for (int i = 1; i <= T; ++ i) {
            for (int j = 1; j <= C; ++ j) {
                for (int k = 1; k <= C; ++ k) {
                    if (dp[i][j] < dp[i - 1][k] + w[k][j] && w[k][j] != 0) {
                        dp[i][j] = dp[i - 1][k] + w[k][j];
                    }
                }
            }
        }
        for (int i = 1; i <= C; ++ i) {
            if (tot < dp[T][i] && end[i] != 0) {
                tot = dp[T][i];
            }
        }
        printf("%d\n", tot);
    }
    return 0;
}

后置知识：

Travelling Salesman Problem（TSP） 是经典的路线问题。它寻求的是旅行者由起点出发，通过所有给定的需求点后，再次返回起点所花费的最小路径成本，也叫旅行商问题。

TSP问题是有 NP 难度的，没有多项式时间的高效解法，所以 TSP 给的 n（城市数）一般都很小。