Re: [問題] 可停留的路線安排程式

作者: outofyou   2016-12-16 12:32:48
: 6. 這一題的特色是:
: (1) 分階段:分成一天一天,每天做一件事。
: (2) 有因果:今天的位置,決定了明天的位置(在九宮格內)。
: (3) 可累積:今天的收益,以後列入總收益。
我做過一些題目之後,也歸納了出了跟DJWS同樣的特色,真是感動。
我繼續思考之後發現,其實這些問題都是最佳化問題,而看題目的時候,
其實要先抓出來題目中的變量有哪些。
例如這一題的變量就是天數、位置(1維或2維或更多維度),
另外要的最佳化結果是可累積的商人收益。
而我用這樣的想法來想的時候,發現背包問題對我來說很特別。
因為我通常都會想用時間(天數)、空間(位置、長度、距離...)當變量,
卻忽略了背包問題還可以用的變量是
物品的種類數、已累積的重量,而要的最佳化結果是可累積的價值總和。
^^^^^^^^^^^^ ^^^^^^^^^^^^
^^^^^^^^
總結:看問題的時候可以觀察題目中有哪些變量、維度,
再按照這些變量、記憶體容量限制、1組解或多組解來設計適合的資料結構儲存資訊。
以上是我的經驗分享,謝謝。
※ 引述《DJWS (...)》之銘言:
: ※ 引述《jakeasa123 (啊斑斑)》之銘言:
: :   先前在Python板發了篇文,也獲得了一些提示,但看了好幾天也試做了幾個版本,還是沒能達到目標,於是來此詢問。
: :   Python板原文:https://www.ptt.cc/bbs/Python/M.1480482142.A.713.html
: 1. 養不教,父之過。教不嚴,師之惰。
: 不必同情老師和同學。他們都有問題。
: 2. 原文的推文都在狀況外。
: 3. 你的問題可以粗略分成程式問題、算法問題。
: 4. 程式問題就是語文問題,另含一點點數學問題。
:   程式語言變化少,只有for if array recursion,通常都有前例可循,其實不難。
:   由於你沒有提供程式碼,這裡假設你沒有程式方面的問題。
: 5. 算法問題就是數學問題。
: 數學問題最困難的地方,就是變化太多、往往沒有前例可循。
: 比方說,在幾何圖形上畫一條補助線,問題豁然開朗,根本莫名其妙。
:   即便背熟算法課本,遇到新的算法問題,通常還是解不開,不必自責。
:  
: 6. 這一題的特色是:
: (1) 分階段:分成一天一天,每天做一件事。
: (2) 有因果:今天的位置,決定了明天的位置(在九宮格內)。
: (3) 可累積:今天的收益,以後列入總收益。
:   通常這種題型,可以用dynamic programming解決。
:   盤面拷貝數份,疊起來,變成三維。
:   一天換一個盤面,往上方走去。
:   程式碼有:一個二維陣列(盤面),兩個二維陣列(dp表格),四層迴圈(填表格)
: 7. 為什麼我會知道那些特色呢?
:   書讀多了、問題看多了,依照經驗歸納出來的。
: 這些特色在不同地方有不同稱呼:
:   例如算法課本裡面的詞彙是「optimal substructure」
:  例如競賽選手所用的詞彙是「無後效性」「狀態轉移」
:   那些特色已經形成了SOP了嗎?
:   就我所知沒有。只能自己看著辦。
: . 為什麼我能聯想到dp呢?
:   因為我曾經遇過類似題目,運氣好。
: 8. 數學問題不只一種解法,這個問題也不只一種解法。
:   如果你想掌握各種解法:
: (1) 靠別人:找一個懂的人,跟他交朋友。往後若有需要,靠交情、花錢請他幫忙。
: (2) 靠自己:讀懂各類算法課程、書籍、論文,情況許可就再念個phd。
: 9. 獲得了「掌握各種解法」的實力之後,有什麼用呢?
:  我看過的有:為興趣、為面試、為逞英雄、為練腦力、為消遣。
:   每個人狀況不一樣,我沒有辦法評論。
: 10. 你們老師同學,也許都想到了這個份上。
: 可能他們已經獲得了「掌握各種解法」的實力。
:   可能他們不想獲得這種實力,因為沒用處、因為關注其他實力、因為太弱、...。
:   因此他們各方評估後,決定簡單教、隨便學就好。
:   與其說他們都有問題,不如說他們都有心思。
作者: outofyou   2016-12-18 22:35:00
修正,而且背包問題用的重量是,"已累積的重量"。

Links booklink

Contact Us: admin [ a t ] ucptt.com