题目描述

从0走经过所有点到n-1，使得路径的权重总和最小

动态规划

动态规划
状态表示：f[i, j] 表示从0达到j点的方案i的路径权重
状态属性：min
状态计算：f[i, j] = min(f[i, j], f[i-(1<<j), k]+w[k][j]) 其中k是存在方案i中与j相连的元素

i存储的是二进制数字，某个位置是1，代表这个方案中存在这个位置的元素

如：
假如走过0,1,4这三个点，我们用二进制10011就可以表示，2,3没走过所以是0

那么走过点的集合i中去除掉点j也很容易表示i - (1 << j)，比方说i是{0,1,4}，j是1，那么i = 10011，(1 << j) = 10，i - (1 << j) = 10001
方案i存在第k个元素 ((i>>k) & 1) != 0

时间复杂度
状态 20*2^20 转移 20
整体的时间复杂度O(20*20*(2^20))

import java.util.*;
import java.io.*;

/**
 * 状态表示：f[i,j] 表示第i个方案中，到达j点的权重
 * 状态属性：min
 * 状态计算：去除j点的方案，通过节点k到达j点的最小方案的权重
 *  f[i, j] = min(f[i,j], f[i-(1<<j), k]+w[k][j]) 其中k是与j相连的元素
 */
public class Main {

    private static int N = 20;
    private static int[][] f = new int[1<<N][N+1];
    private static int[][] w = new int[N+1][N+1];

    public static void main(String[] args) throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] line = reader.readLine().split(" ");
        int n = Integer.parseInt(line[0]);

        for (int i=0; i<n; i++) {
            line = reader.readLine().split(" ");
            for (int j=0; j<n; j++) {
                w[i][j] = Integer.parseInt(line[j]);
            }
        }

        // 求最小值记得初始化哈~~~
        for (int i=0; i<(1<<n); i++) {
            Arrays.fill(f[i], Integer.MAX_VALUE/2);
        }
        f[1][0] = 0;

        for (int i=0; i<(1<<n); i++) {
            for (int j=0; j<n; j++) {
                // 方案中存在第j个元素
                if (((i>>j) & 1) != 0) {
                    for (int k=0; k<n; k++) {
                        // 方案中i中存在第k个元素
                        if ((((i-(1<<j))>>k) & 1) != 0) {
                            f[i][j] = Math.min(f[i][j], f[i-(1<<j)][k] + w[k][j]);
                        }
                    }
                }
            }
        }

        System.out.println(f[(1<<n)-1][n-1]);
    }
}

参考