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

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

看板Prob_Solve (計算數學 Problem Solving)作者jakeasa123 (啊斑斑)時間8年前 (2016/12/13 14:56)推噓3(3推 0噓 10→)

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

　　先前在Python板發了篇文，也獲得了一些提示，但看了好幾天也試做了幾個版本，還是沒能達到目標，於是來此詢問。　　Python板原文：https://www.ptt.cc/bbs/Python/M.1480482142.A.713.html 　　程式的概念是，有個商人每天能走零格（停留）或一格（包含斜走）方格，他有ｎ天可以經商，要安排出這ｎ天他能獲得最大利益的路線。經商獲利（雖然原要求是1xx*1xx格，這邊簡化5*5）： ┌－－┬－－┬－－┬－－┬－－┐ ｜　40｜　30｜　20｜　10｜　95｜ ├－－┼－－┼－－┼－－┼－－┤ ｜　50｜　40｜　35｜　30｜　85｜ ├－－┼－－┼－－┼－－┼－－┤ ｜　60｜　45｜起｜　25｜　80｜ ├－－┼－－┼－－┼－－┼－－┤ ｜　70｜　10｜　15｜　20｜　75｜ ├－－┼－－┼－－┼－－┼－－┤ ｜　80｜　50｜　55｜　65｜　70｜ └－－┴－－┴－－┴－－┴－－┘　（起點處：25）　　如果只有一天，會是往左走停在45；兩天的話，會是往右上的30+95；三天的話，30+95+95（停留）……以此類推。　　（我知道格子給的數字讓這例子很爛QQ）　　有想過用迴圈把「起點～每一格」的最大距離都算出來，可是最邊界的方格在中途的自由步數有限和一些原因（滿久以前想的，記不起來……），這個方法應該行不通。　　自起點開始計算的只會找到每步的最大值，而不是時間內可行走得到的最大值，所以這個應該也行不通。　　留言提及的DP看下來是最接近我要求的，只是試了好幾次都做不成功，更別說還要記錄程式是怎麼走的（方向或走到哪格）…… 　　小弟雖是資工的，但教授教得不深（原本還滿氣教授怎麼都教得這麼基礎，後來想到四年級同班還有人來問我怎麼寫for和if就開始同情教授了），沒有學到很多跟程式有關的；試著在課餘時間自學也幾年了，但可能方向不對或是沒有足夠深入，所以現在這個做不出來…… 　　懇請諸位前輩指點！小弟也在此先向前輩致謝花時間閱讀與思考！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.134.106.248 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1481612204.A.6F8.html