ㄜ....我之前那篇好像明顯的超越課程進度的樣子....
(這並不跟我的程設強度正相關....)
可是,既然是我提出這些名詞的,
我想,我應該還是要盡我那淺薄的知識解釋一下
(其實我比較希望有那位高人來救我....)
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