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

Re: [問題] Maximum Product

看板Prob_Solve (計算數學 Problem Solving)作者 (簡哥)時間8年前 (2016/09/10 01:15), 8年前編輯推噓6(6推 0噓 11→)
留言17則, 4人參與, 最新討論串2/4 (看更多)
※ 引述《cutekid (可愛小孩子)》之銘言： : 給定一個數字 N (由 1 ~ 9組成) : 其中插入 K 個乘號，使最後相乘的值要最大 : 舉例: : N = 746589, K = 2, 最大值 = 7465 x 8 x 9 : N = 1111114, K = 3, 最大值 = 11 x 11 x 11 x 4 : 請問這題除了 C(長度 - 1,K) 暴力搜尋 : 還有什麼比較好的算法嗎 : 謝謝 ^_^ 寫一下我的想法,有錯請告知 這裡就先不考慮 overflow 的問題 設計函式 max_product( number, k ) 代表在 number 裡插入 k 個乘號 以你第一個例子 要求解 max_product( 746589, 2 ) 它的解是 7 * max_product( 46589, 1 ) 74 * max_product( 6589, 1 ) 746 * max_product( 589, 1 ) 7465 * max_product( 89, 1 ) 這其中一個 74658 * max_product( 9, 1 ) 因為 9 沒法插一個乘號進去所以不算 然後每一個結果都可以存下來,遞迴就不用每次跑 算是 top-down 的 DP 吧,複雜度估計大概是 O( nk ) 遞迴的終止條件是 k = 0 感覺用 python 會比較好寫XD -- 　Ｔｈｉｓ　 ████ ███ ███◣ ████ ███◣ ◥◣ ◢◤ ████ █ ████ ████ ████ ◣█◢ ｉｓ ████ █ ███▎ ████ ███◤ █ █ ████ █ █████ ████ █◥◣ ██ ｄｉｂｅｒｙ ███◤ ███ ███◤ ████ ██◥◣ ███ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.184.18.6 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1473441321.A.445.html
推
09/10 01:19, , 1F
top-down 是遞迴, bottom-up 才叫 DP
09/10 01:19, 1F
→
09/10 01:19, , 2F
然後 top-down 加記錄的叫做筆記法 (memoization)
09/10 01:19, 2F
這是我從 Wiki 的頁面上找來的 通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次， 從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化（en:memoization） 存儲，以便下次需要同一個子問題解之時直接查表。 這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。 top-down 的,有用到記憶搜索,應該也可以算 DP 吧?
→
09/10 01:20, , 3F
這題要 bottom-up 當然也行, 從 k = 0 開始
09/10 01:20, 3F
→
09/10 01:20, , 4F
每個 k 枚舉所有乘號位置去計算
09/10 01:20, 4F
推
09/10 01:45, , 5F
不過一樓這種分法碰到有 lazy data structure 的語言就
09/10 01:45, 5F
→
09/10 01:45, , 6F
很難分清楚了XD
09/10 01:45, 6F
→
09/10 03:17, , 7F
剪枝條件是什麼，全跑完做法討論串原po已經講了。
09/10 03:17, 7F
推
09/10 08:05, , 8F
只要用 memoization 就好了 應該不太需要剪枝吧
09/10 08:05, 8F
對啊,有把結果記下來應該就不需要剪枝了吧? 全跑完的作法不是算排列組合嗎?這個作法不是暴力搜尋
推
09/10 08:44, , 9F
有 memoization 就已經不是全跑完了吧
09/10 08:44, 9F
→
09/10 12:58, , 10F
請問記憶之前參考條件為何。這一格參考上一層該格的條件
09/10 12:58, 10F
※ 編輯: dibery (111.184.18.6), 09/10/2016 17:47:05
推
09/11 03:31, , 11F
>suhorng 所以 DP 本質還是遞迴啊, 只是計算順序的差別而已
09/11 03:31, 11F
→
09/11 03:31, , 12F
lazy eval 就是能夠讓 top-down 定義的東西能 bottom-up 求
09/11 03:31, 12F
→
09/11 03:32, , 13F
而 DP 只是我們自己去整理到底 bottom-up 一共要哪些東西
09/11 03:32, 13F
→
09/11 03:32, , 14F
一口氣算完之後堆疊上來而已
09/11 03:32, 14F
推
09/13 10:52, , 15F
基本上條件就是這個 max_product 的兩個參數. 由於每一次
09/13 10:52, 15F
→
09/13 10:52, , 16F
插入乘號兩邊都會變小, 所以 max_product 不會循環參考
09/13 10:52, 16F
→
09/13 10:53, , 17F
本格 max_product 就是 max prefix*max_p..(suffix,num)
09/13 10:53, 17F
‣ 更多 dibery 的文章
文章代碼(AID): #1NqkufH5 (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 2 之 4 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共4篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 dibery 的文章
文章代碼(AID): #1NqkufH5 (Prob_Solve)