一個月前被拉進了一個微信群，名字叫《明日都是大佬》，群里有20多個人，都是正在跳槽的，目標是年薪30w！投簡歷、筆試、面試后都相互分享，互通有無你懂的。拉我進群是幫忙解答一些難題，很多題目還是蠻有意思的，近期計劃整理下然后給大家分享，其中一道順豐技術內(nèi)測題引起了我們的討論！

不得不說，進群不到一個月，2/3的人都已經(jīng)拿到心儀的offer！

順豐-配送湊單

順豐快遞在高級開發(fā)崗位的筆試題里面有這么個問題:

假設一臺卡車可以裝載100立方米的貨物，然后貨物信息如下，如何搭配才能讓卡車裝下最大重量的貨物(編碼實現(xiàn))？如果再限制總重量不能得超過20噸，結果如何？

貨物清單：

貨物A: 3立方米 0.4噸

貨物B: 5立方米 0.7噸

貨物C: 7立方米 1.0噸

貨物D: 11立方米 1.7噸

貨物E: 13立方米 2.2噸

這題說答案沒意思，因為思路才是考核的地方。首先肯定不能窮舉，累死都算不出來，肯定得有個算法完成。下面來一波思路分析：

1

卡車能裝下，也就是物品總體積不能超過100立方米。

2

重量最大，也就是是找單位體積重量最大的，發(fā)現(xiàn)貨物越大，平均重量越大，所以優(yōu)先體積大的。

3

體積大的并不能充分填滿空間，再去填充體積小的，這是貪婪算法的實現(xiàn)，但不一定得到最優(yōu)解，在總空間固定的情況下，該如何獲取最佳結果呢？動態(tài)規(guī)劃！

動態(tài)規(guī)劃：動態(tài)規(guī)劃則是從底部開始，解決小的問題同時把它們合并形成大問題的一個完整解決方案。

4

動態(tài)規(guī)劃的思路是分別從貨物A找出最優(yōu)解，加入貨物B后的最優(yōu)解，加入貨物C后的最優(yōu)解，加入貨物D后的最優(yōu)解，加入貨物E后的最優(yōu)解，甚至還可以有更多的貨物都可以的

網(wǎng)易-地圖尋址

網(wǎng)易游戲后端.NET Core開發(fā)崗面試里面，有個很有趣的問題是游戲地圖尋址，問題大致描述如下(非原題)：

下面是一個游戲地圖抽象，箭頭代表可以前進的方向，數(shù)字代表距離。如果玩家要從位置A移動到到位置E，用窮舉法算出的最短距離和路徑是多少？用貪心算法呢？二者該如何選擇？

窮舉法：最短路徑A-C-B-E，距離是28

貪心算法：最短路徑A-C-F-E，距離是30

窮舉法只是用在結果集較少的情況下，通過羅列全部的結果得到最優(yōu)解，而貪心算法(尋址的時候還有個專門的名字叫Dijkstra)，是利用局部最優(yōu)解最終拼裝得到全局的結果，有可能不是最好結果(如本題)，但能在大數(shù)據(jù)標本下，能獲得的相對優(yōu)秀解的一種算法。