ㄜ....我之前那篇好像明顯的超越課程進度的樣子.... (這並不跟我的程設強度正相關....) 可是,既然是我提出這些名詞的, 我想,我應該還是要盡我那淺薄的知識解釋一下 (其實我比較希望有那位高人來救我....) 1.Greedy中譯貪婪法 簡單說就是像老師講的釀,先填大的,在依次填入較小的 典型問題:找硬幣 例如,今天要湊出87元好了,目標是讓硬幣數最小 那用新台幣的硬幣來看,我們就先用一個50元,接著是10元三個 一個5元、兩個1元, 這就是最佳解(反正很少看到莫那魯道,就忽略一下) holymars所提供的補充是,在每個硬幣的幣值都是比他大的硬幣幣值的因數時, Greedy確保有最佳解,原因是,小的塞不滿,大的也一定填不滿 方法一的修正,可說便是由此而來,因為5是25的因數,一定能填滿貨櫃 之後2是8的因數,所以應該就能用Greedy找到最佳解 遺憾的是,後來我找到反例...(原本以為終於可以簡單寫完這題...) 2.BFS=Breadth(?) First Search,廣度優先搜尋 其實這是對圖形進行"拜訪"的一種方法(假設我沒記錯...) ....我需要圖...可是我不會用bbs畫圖... 總之,就這題來講,現在如果8還有剩,就把放一個8的狀況,存起來 ,然後塞到某個暫存的地方(這有名字的,可是我不想再惹麻煩了...) 對5、2做一樣的事情,然後從剛剛塞東西的地方,把最先放進去的那個拿出來 重複這樣的動作,並且對每個填完的狀況比較,輸出貨櫃數最小的解 簡而言之,把每種放置順序都找出來,其實這就是暴力法啦... 所以我說...應該確定能找到最佳解...可能也最花時間 3.DP=Dynamic Programming,動態規劃 一言以蔽之,建表!!!,(其實我最不敢說我會的就是這種演算法) 用這題作範例,先考慮貨櫃大小只有1的狀況,把此時的狀況記在表中 再看大小為2,3,4.....的情形,然後視題目要求,找出最佳解, 也許這題不是醬DP...有可能我弄錯意思, 基本上 這些都是資料結構與演算法的東西,沒記錯的話,這是大二的課... 所以,絕對不要在意自己不知道這些東西, 這一切都是因為教授自己以為Greedy一定有最佳解, (就像香蕉講的,要是她xxx有給數字,我們或許可以判斷 到底是不是只要Greedy就行了) 結果不行(只要有反例就算不行) --------------------------------這是亂入--------------------------- 在物理上 推翻一條定理很簡單,找到反例就行了, 讓假說變定理要很久,有證明,不夠,要經過長時間的驗證 ---《愛因斯坦怎麼想》似乎是從這出來的... --------------------------------亂入結束--------------------------- 所以,這題突然變成難度極高的問題(就我以大一計程的程度來看) 我也覺得突然爆Greedy那些的出來很詭異... 真希望...題目改成某個人在用Greedy裝貨,要我們預測結果就好了.... 絕對花的時間不會太長 -- 人類是絕對無法真正彼此了解的,但人類卻總是試著了解他人 人類就是這麼悲哀的生物 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.239.64