旅行商问题

最优子结构证明

https://blog.csdn.net/qq_39559641/article/details/101209534
写的不错

简简单单

import javax.swing.text.Style;
import java.util.Scanner;
import java.util.*;


public class Main{


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] map = new int[N][N];

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                map[i][j] = sc.nextInt();
            }
        }
        //初始化完毕

        int min_cost = TSP(map,N);
        System.out.println(min_cost);

    }

    public static int TSP(int[][] map, int N){
        // 代表从 i点 到 初始点 经过集合V中的每一个点，并且只经过一次的最短路径
        // v最多包含N-1个点  因此 V最多含有 2^(N-1)中状态 每个点使用二进制中的0或者1表示
        int[][] dp = new int[N][(int) (Math.pow(2,N-1))];

        //当前点为i
        //如果 V 是空 dp=c【i,s】
        //否则 V = min（遍历k属于V， c【i，k】 + dp[k][V-k]）;
        // V 不能包含 i节点本身

        //假设从 0 开始环游
        for(int j=0;j<dp[0].length;j++){
            for (int i=0;i<dp.length;i++){
                dp[i][j] = Integer.MAX_VALUE;
                // 空状态 j=0  i不经过任何点 直接到0
                if( j == 0 && i!=0) dp[i][j] = map[i][0];
                // v 不为空
                else{
                    // V中包含i节点本身 直接
                    if( (j & 1<<(i-1)) !=0 ) continue;

                    for(int k=1;k<N;k++){
                        // 如果k节点在V中
                        if( (j>>(k-1) & 1) ==1 ){
                            int newstate = j ^ (1<<(k-1));  // k节点抹去 异或操作
                            dp[i][j] = Math.min(dp[i][j],map[i][k] + dp[k][newstate] );
                        }
                    }
                }
            }
        }
        //循环结束 状态dp更新完成
        return  dp[0][dp[0].length-1];
    }
}