标签搜索

目 录CONTENT

文章目录

字节跳动---毕业旅行问题.md

小小城
2022-05-02 / 0 评论 / 0 点赞 / 7 阅读 / 2,585 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

毕业旅行问题.md
date: 2021-08-22 12:11:39.91
updated: 2021-08-22 12:11:39.91
url: /2021/08/22/字节跳动---毕业旅行问题md
categories:
tags:

字节跳动---毕业旅行问题

@[toc]

一、问题描述

小明目前在做一份毕业旅行的规划。打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去一次。由于经费有限,希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小车费花销

输入描述:

城市个数n(1<n≤20,包括北京)

城市间的车票价钱 n行n列的矩阵 m[n][n]

输出描述:

最小车费花销 s

输入例子1:

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出例子1:

13

例子说明1:

共 4 个城市,城市 1 和城市 1 的车费为0,城市 1 和城市 2 之间的车费为 2,城市 1 和城市 3 之间的车费为 6,城市 1 和城市 4 之间的车费为 5,依次类推。假设任意两个城市之间均有单程票可购买,且票价在1000元以内,无需考虑极端情况。

二、分析

方法一:回溯【超时】

把所有的解通过一棵树表达出来,然后通过深度优先遍历,找到一个解的时候就将其记录下来,最后输出最小的解即可

在这里插入图片描述
如图所示,从根节点到叶子节点的所经过的节点就是其路径,每个边的长度之和就是总车票价格。

当然还有一种优化的方法,就是在遍历过程中,如果发现此时路径长度已经超出了之前找到的最小路径长度,就可以进行剪支操作,即不再遍历。

这种方法的时间复杂度为$O(n!)O(n!)O(n!)$,当n大于12之后,其计算时间就已经非常大了。这种方法会因为超时无法通过所有的测试数据。

方法二:动规

  •  第一步:明确动态规划的 状态和选择

对于这道题,状态无非就是 旅行出发的起点和经过的城市,所以用一个二维dp数组来进行递归

旅行的出发点 还好说, 用数组的索引 就可以直接表示,关键是怎么表示已经经过的城市,经过的城市不可能只有一个,一个数组的索引肯定不能够表示全部,所以用什么来表示这个状呢???

所以用数组的下标索引当成一个位图,用其中的 每个bit位代表已经经过哪些城市

虽然找到解决经过的城市的方法,但是还要考虑怎么设置进比特位,因为我们在进行判断的时候肯定需要知道对应bit位是那个城市,所以还需要考虑bit位的设计

规定:从1到n-1(n为城市的个数) 用二进制表示的话,刚好可以映射成除了0号城市外的剩余n-1个城市在不在子集n[j],1代表在,0代表不在

例:若有总共有4个城市的话,除了第0号城市,对于1-3号城市
111 = V-1 = 2^3 - 1 = 7 ,从高位到低位表示3到1号城市都在子集中
而101 = 5 ,表示3,1号城市在子集中,而其他城市不在子集中

所以该索引的大小为:1 << n(n为城市的个数)

int stateNum = 1 << n;
    // dp[i][j]中的i是一个二进制形式的数,表示经过城市的集合,如0111表示经过了城市0,1,2
    // dp[i][j]表示经过了i中的城市,并且以j结尾的路径长度
    vector<vector<int> > dp(stateNum,vector<int>(n,MAX));

dp[i][j]的含义:中的i是一个二进制形式的数,表示经过城市的集合,如0111表示经过了城市0,1,2,表示经过了i中的城市,并且以j城市结尾的路径(钱)长度

第二步:明确base case

这个就很容易确定

dp[1][0] = 0; //从城市0出发,所以经过城市0,以城市0结尾的路径为0

从城市0出发,所以经过城市0,以城市0结尾的路径为0

第三步:找状态转移方程

👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇
在代码中

三、代码


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int getAns(vector<vector<int>> &nums)
{
    const int MAX = 0x0fffffff;
    int n = nums.size();
    int stateNum = 1 << n;
    // dp[i][j]中的i是一个二进制形式的数,表示经过城市的集合,如0111表示经过了城市0,1,2
    // dp[i][j]表示经过了i中的城市,并且以j结尾的路径长度
    vector<vector<int> > dp(stateNum,vector<int>(n,MAX));
    dp[1][0] = 0; //从城市0出发,所以经过城市0,以城市0结尾的路径为0
    
    //从城市0出发,更新和其他城市的距离
    for(int i=1;i<stateNum;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(dp[i][j] != MAX)
            { 
            	//如果已经访问过
                for(int k=0;k<n;k++)
                {
                    if( (i & (1 << k) ) == 0)
                    { 
                        //没有访问过k,且从这里到k的距离小于原来的距离,则更新
                        dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k],dp[i][j] + nums[j][k]);
                    }
                }
            }
        }
    }
    
    int res = MAX;
    for(int i=1;i<n;i++)
    {
        res = min(res,dp[stateNum-1][i] + nums[i][0]);
    }
    return res;
}

int main(int argc, char const *argv[])
{
   int n;
    while(cin>>n)
    {
        vector<vector<int>> edges(n,vector<int>(n,0));
        
        int x;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                cin>>edges[i][j];
            }
        }
        cout<<getAns(edges)<<endl;
    }
    return 0;
}
0

评论区