PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者outofyou時間8年前 (2016/12/16 12:32)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串4/5 (看更多)

: 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. 你們老師同學，也許都想到了這個份上。 : 可能他們已經獲得了「掌握各種解法」的實力。 : 　　可能他們不想獲得這種實力，因為沒用處、因為關注其他實力、因為太弱、...。 : 　　因此他們各方評估後，決定簡單教、隨便學就好。 : 　　與其說他們都有問題，不如說他們都有心思。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.62.111.183 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1481862770.A.456.html