毕业旅行问题

思路

首先容易想到的思路就是进行深度优先遍历，将所有可能的结果算出来求其最小值。但是这种算法明显时间复杂度过大，不在考虑范围内。
对于这种求最值的问题，我们一般想到用动态规划的方式求解。动态规划是将一个大的问题分解成几个小的问题。我们需要确定我们的dp数组所代表的含义，并找出递推公式。
对于这道题我们所要求的是从0号城市出发(即北京)经过其他所有城市(集合P)最终又回到0号城市的最小费用M;显然M等于Min{P中的一个城市City经过P-{City}城市最终又回到0号城市的最小费用+0号城市到City城市的费用}。于是我们可以定义dp[i][P] = Min{dp[j][P-j]+D}。其中P是城市集合。
我们该如何表示该集合，我们可以利用状态压缩的想法。将每一个城市作为一个二进制数的一位，一个int型数最多可以表示32个city.满足该题的最多20个城市。
dp[i][0]代表从i城市出发不经过其他城市直接到0号城市。其值为dp[i][0] = matrix[i][0]
我们最终的答案为dp[0][P]。其中P包含了除0号城市以外其他所有的城市。由上面所述，我们可以根据大集合的值是由小集合决定的。故第一层循环为循环所有的集合数。然后便是选取起点，再之后循环下一城市即可。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
        public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
                int n  = scanner.nextInt();
                scanner.nextLine();
                int[][] matrix = new int[n][n];
                for(int i = 0 ; i < n; i++){
                        for(int j  = 0; j < n; j++){
                                matrix[i][j] = scanner.nextInt();
                        }
                        scanner.nextLine();
                }
                int[][] dp = new int[n][1<<(n-1)];
                for(int i = 0 ; i < n;i++){
                        dp[i][0] = matrix[i][0];
                }
                //0不包含在dp数组第二维中，故i<1<<n-1
                for(int i =1 ; i <(1<<(n-1));i++){
                        //选取起点
                        for(int j =0 ; j < n ;j++){
                                dp[j][i] = Integer.MAX_VALUE>>1;
                              if(check(i,j))
                                      continue;
                              for(int k = 1 ;k<n;k++){
                                      if(check(i,k)){
                                              int tem = unmask(i,k);
                                              dp[j][i] = Math.min(dp[j][i],dp[k][tem]+matrix[j][k]);
                                      }
                              }
                        }
                }
                System.out.println(dp[0][(1<<(n-1))-1]);

        }
        public static boolean check(int a, int b){
                if(b==0){
                        return false;
                }
                //如果等于0说明b不包含在a中。
                return (a&(1<<(b-1)))!=0;
        }
        public static int unmask(int a,int b){
                return  a&(~(1<<(b-1)));
        }
}