Re: [問題] Maximum Product
※ 引述《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
09/10 01:19, 1F
→
09/10 01:19, , 2F
09/10 01:19, 2F
這是我從 Wiki 的頁面上找來的
通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，
從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化（en:memoization）
存儲，以便下次需要同一個子問題解之時直接查表。
這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。
top-down 的,有用到記憶搜索,應該也可以算 DP 吧?
→
09/10 01:20, , 3F
09/10 01:20, 3F
→
09/10 01:20, , 4F
09/10 01:20, 4F
推
09/10 01:45, , 5F
09/10 01:45, 5F
→
09/10 01:45, , 6F
09/10 01:45, 6F
→
09/10 03:17, , 7F
09/10 03:17, 7F
推
09/10 08:05, , 8F
09/10 08:05, 8F
對啊,有把結果記下來應該就不需要剪枝了吧?
全跑完的作法不是算排列組合嗎?這個作法不是暴力搜尋
推
09/10 08:44, , 9F
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
09/11 03:31, 11F
→
09/11 03:31, , 12F
09/11 03:31, 12F
→
09/11 03:32, , 13F
09/11 03:32, 13F
→
09/11 03:32, , 14F
09/11 03:32, 14F
推
09/13 10:52, , 15F
09/13 10:52, 15F
→
09/13 10:52, , 16F
09/13 10:52, 16F
→
09/13 10:53, , 17F
09/13 10:53, 17F
討論串 (同標題文章)