作者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/cn.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