首页 > 试题广场 >

使用动态规划方法,我们首先求解子问题,然后选择哪些子问题用来

[问答题]
使用动态规划方法,我们首先求解子问题,然后选择哪些子问题用来构造原问题的最优解。Capulet教授认为,我们不必为了求原问题的最优解而总是求解出所有子问题。她建议,在求矩阵链乘法问题的最优解时,我们总是可以在求解子问题之前选定AiAi+1...Aj的划分位置Ak(选定的k使得pi-1pkpj最小)。请找出一个反例,证明这个贪心算法可能生成次优解。

这道题你会答吗?花几分钟告诉大家答案吧!