字節(jié)跳動(dòng)—畢業(yè)旅行問題

文章目錄

• • 字節(jié)跳動(dòng)---畢業(yè)旅行問題
  • 一、問題描述
  • 二、分析
  • 三、代碼

一、問題描述

小明目前在做一份畢業(yè)旅行的規(guī)劃。打算從北京出發(fā)，分別去若干個(gè)城市，然后再回到北京，每個(gè)城市之間均乘坐高鐵，且每個(gè)城市只去一次。由于經(jīng)費(fèi)有限，希望能夠通過合理的路線安排盡可能的省一些路上的花銷。給定一組城市和每對(duì)城市之間的火車票的價(jià)錢，找到每個(gè)城市只訪問一次并返回起點(diǎn)的最小車費(fèi)花銷。

輸入描述:

城市個(gè)數(shù)n（1<n≤20，包括北京）城市間的車票價(jià)錢 n行n列的矩陣 m[n][n]

輸出描述:

最小車費(fèi)花銷 s

輸入例子1:

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

輸出例子1:

13

例子說明1:

共 4 個(gè)城市，城市 1 和城市 1 的車費(fèi)為0，城市 1 和城市 2 之間的車費(fèi)為 2，城市 1 和城市 3 之間的車費(fèi)為 6，城市 1 和城市 4 之間的車費(fèi)為 5，依次類推。假設(shè)任意兩個(gè)城市之間均有單程票可購買，且票價(jià)在1000元以內(nèi)，無需考慮極端情況。

二、分析

方法一：回溯【超時(shí)】

把所有的解通過一棵樹表達(dá)出來，然后通過深度優(yōu)先遍歷，找到一個(gè)解的時(shí)候就將其記錄下來，最后輸出最小的解即可

如圖所示，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所經(jīng)過的節(jié)點(diǎn)就是其路徑，每個(gè)邊的長(zhǎng)度之和就是總車票價(jià)格。

當(dāng)然還有一種優(yōu)化的方法，就是在遍歷過程中，如果發(fā)現(xiàn)此時(shí)路徑長(zhǎng)度已經(jīng)超出了之前找到的最小路徑長(zhǎng)度，就可以進(jìn)行剪支操作，即不再遍歷。

這種方法的時(shí)間復(fù)雜度為$O(n!)O(n!)O(n!)$，當(dāng)n大于12之后，其計(jì)算時(shí)間就已經(jīng)非常大了。這種方法會(huì)因?yàn)槌瑫r(shí)無法通過所有的測(cè)試數(shù)據(jù)。

方法二：動(dòng)規(guī)

• 第一步：明確動(dòng)態(tài)規(guī)劃的 狀態(tài)和選擇

對(duì)于這道題，狀態(tài)無非就是 旅行出發(fā)的起點(diǎn)和經(jīng)過的城市，所以用一個(gè)二維dp數(shù)組來進(jìn)行遞歸

旅行的出發(fā)點(diǎn) 還好說， 用數(shù)組的索引 就可以直接表示，關(guān)鍵是怎么表示已經(jīng)經(jīng)過的城市，經(jīng)過的城市不可能只有一個(gè)，一個(gè)數(shù)組的索引肯定不能夠表示全部，所以用什么來表示這個(gè)狀呢？？？

所以用數(shù)組的下標(biāo)索引當(dāng)成一個(gè)位圖，用其中的 每個(gè)bit位代表已經(jīng)經(jīng)過哪些城市

雖然找到解決經(jīng)過的城市的方法，但是還要考慮怎么設(shè)置進(jìn)比特位，因?yàn)槲覀冊(cè)谶M(jìn)行判斷的時(shí)候肯定需要知道對(duì)應(yīng)bit位是那個(gè)城市，所以還需要考慮bit位的設(shè)計(jì)

規(guī)定：從1到n-1（n為城市的個(gè)數(shù)） 用二進(jìn)制表示的話，剛好可以映射成除了0號(hào)城市外的剩余n-1個(gè)城市在不在子集n[j]，1代表在，0代表不在

例：若有總共有4個(gè)城市的話，除了第0號(hào)城市，對(duì)于1-3號(hào)城市
111 = V-1 = 2^3 - 1 = 7 ，從高位到低位表示3到1號(hào)城市都在子集中
而101 = 5 ，表示3,1號(hào)城市在子集中，而其他城市不在子集中

所以該索引的大小為：1 << n（n為城市的個(gè)數(shù)）

int stateNum = 1 << n;// dp[i][j]中的i是一個(gè)二進(jìn)制形式的數(shù)，表示經(jīng)過城市的集合，如0111表示經(jīng)過了城市0,1,2// dp[i][j]表示經(jīng)過了i中的城市，并且以j結(jié)尾的路徑長(zhǎng)度vector<vector<int> > dp(stateNum,vector<int>(n,MAX));

dp[i][j]的含義：中的i是一個(gè)二進(jìn)制形式的數(shù)，表示經(jīng)過城市的集合，如0111表示經(jīng)過了城市0,1,2，表示經(jīng)過了i中的城市，并且以j城市結(jié)尾的路徑（錢）長(zhǎng)度

第二步：明確base case

這個(gè)就很容易確定

dp[1][0] = 0; //從城市0出發(fā)，所以經(jīng)過城市0，以城市0結(jié)尾的路徑為0

從城市0出發(fā)，所以經(jīng)過城市0，以城市0結(jié)尾的路徑為0

第三步：找狀態(tài)轉(zhuǎn)移方程

👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇
在代碼中

三、代碼

#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是一個(gè)二進(jìn)制形式的數(shù)，表示經(jīng)過城市的集合，如0111表示經(jīng)過了城市0,1,2// dp[i][j]表示經(jīng)過了i中的城市，并且以j結(jié)尾的路徑長(zhǎng)度vector<vector<int> > dp(stateNum,vector<int>(n,MAX));dp[1][0] = 0; //從城市0出發(fā)，所以經(jīng)過城市0，以城市0結(jié)尾的路徑為0//從城市0出發(fā)，更新和其他城市的距離for(int i=1;i<stateNum;i++){for(int j=0;j<n;j++){if(dp[i][j] != MAX){ //如果已經(jīng)訪問過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; }

總結(jié)

以上是生活随笔為你收集整理的字节跳动---毕业旅行问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。