作者dibery (簡哥)
看板Prob_Solve
標題Re: [問題] Maximum Product
時間Sat Sep 10 01:15:15 2016
※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1473441321.A.445.html
1F：推 LPH66: top-down 是遞迴, bottom-up 才叫 DP 09/10 01:19
2F：→ LPH66: 然後 top-down 加記錄的叫做筆記法 (memoization) 09/10 01:19
這是我從 Wiki 的頁面上找來的
通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，
從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化（en:memoization）
存儲，以便下次需要同一個子問題解之時直接查表。
這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。
top-down 的,有用到記憶搜索,應該也可以算 DP 吧?
3F：→ LPH66: 這題要 bottom-up 當然也行, 從 k = 0 開始 09/10 01:20
4F：→ LPH66: 每個 k 枚舉所有乘號位置去計算 09/10 01:20
5F：推 suhorng: 不過一樓這種分法碰到有 lazy data structure 的語言就 09/10 01:45
6F：→ suhorng: 很難分清楚了XD 09/10 01:45
7F：→ pttworld: 剪枝條件是什麼，全跑完做法討論串原po已經講了。 09/10 03:17
8F：推 FRAXIS: 只要用 memoization 就好了 應該不太需要剪枝吧 09/10 08:05
對啊,有把結果記下來應該就不需要剪枝了吧?
全跑完的作法不是算排列組合嗎?這個作法不是暴力搜尋
9F：推 suhorng: 有 memoization 就已經不是全跑完了吧 09/10 08:44
10F：→ pttworld: 請問記憶之前參考條件為何。這一格參考上一層該格的條件 09/10 12:58
※ 編輯: dibery (111.184.18.6), 09/10/2016 17:47:05
11F：推 LPH66: >suhorng 所以 DP 本質還是遞迴啊, 只是計算順序的差別而已 09/11 03:31
12F：→ LPH66: lazy eval 就是能夠讓 top-down 定義的東西能 bottom-up 求 09/11 03:31
13F：→ LPH66: 而 DP 只是我們自己去整理到底 bottom-up 一共要哪些東西 09/11 03:32
14F：→ LPH66: 一口氣算完之後堆疊上來而已 09/11 03:32
15F：推 suhorng: 基本上條件就是這個 max_product 的兩個參數. 由於每一次 09/13 10:52
16F：→ suhorng: 插入乘號兩邊都會變小, 所以 max_product 不會循環參考 09/13 10:52
17F：→ suhorng: 本格 max_product 就是 max prefix*max_p..(suffix,num) 09/13 10:53