算法设计与分析试题及答案(3)

很好的复习资料!

一、

已知Ak (aij(k))ri*ri 1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，

求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。（要求：给出计算步骤）（20分）

答：使用动态规划算法进行求解。 求解矩阵为：【每个矩阵18分】

因此，最佳乘积序列为（A1A2）（（A3A4）（A5A6）），共执行乘法2010次。【结论2分】 二、

假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容

量M＝150，如果使用贪心方法求解此背包问题，请回答：（20分）。

（1） 对各个物品进行排序时，依据的标准都有哪些？

（2） 使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。 （3） 上述解中哪个是最优的？

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库算法设计与分析试题及答案(3)在线全文阅读。