哈工大數據結構實驗三——設備更新問題

1.實驗要求

2.構造圖求解

初看這道題我想用動態規劃求解，不過由於本章學的是圖的最短路徑問題，所以我使勁的想構造圖來解決這個問題。
構造的圖是有向圖，因爲時間是順着流的。
解題思路:

1. 圖的每個頂點的編號表示的是第幾年初，比如頂點1表示第1年初。
2. 圖中任意兩個頂點i和j有一條有向邊，表示在第i年購買了一臺機器，這臺一直用到了第j年。(第j年沒用這臺機器)
3. 圖的任意兩個頂點之間i和j的權重，表示第i年到第j年的使用機器的費用。(不包括第j年)

第i個節點到第j個節點的費用怎麼算呢？就是等於第i年購買某臺機器的費用+ 第i年到第j年的維修費用。

4. 除了給出的n年需要構造n個節點之外，我需要藉助第n+1個節點。所有的其他頂點都有一條邊指向第n+1個節點，表示這n年的總開銷。

想一想爲什麼？

因爲我的節點的含義是每一年的開始。我們要統計n年的費用肯定得統計到第n年結束。也就是一直統計到第n+1個節點。
所有的其他頂點都有一條邊指向第n+1個節點表示我在其他的某年購買了一臺機器我就不再購買機器了，一直用到第n年年底。

5. 因此我們只要把所求的問題構造出圖，然後問題的求解就是求第1個節點到第n+1個節點的最短路徑。

3.舉例子說明

拿實驗要求給的例子說明

那麼我們構造的有向圖爲：

上圖的鄰接矩陣爲
(節點0表示第1年，因爲數組是從下標0開始存儲的，所以就這樣表示)
第i年到第j年的權重=第i年機器的費用+第i年到第j年的維修費

如上圖所示，當把圖構造出來後，只需要利用最短路徑算法(Dijkstra算法或者Floyd算法即可求解出來。)

4.圖的最短路徑求解

我在另一片博客詳細講解了Dijkstra算法和Floyd算法。詳細講解了單源最短路徑和任意兩個最短路徑的求解方法。

最短路徑算法，點擊即可直達！

因此，你需要做的就是按照我上述的思路建立一個有向圖，然後跑一遍圖最短路徑算法即可。

具體代碼暫時不公佈，沒時間寫。我自己也有很多實驗ddl要寫，哭了。。

動態規劃算法暫時沒時間寫，以後再公佈。。

點個關注，點個贊再走啊啊啊