【读书笔记】算法漫步 第20章

问题17投资

合理分配资源，投入到某些事项上，希望得到最好的综合汇报，这类追求很有意义，得到了广泛的研究。当然，如果在现实中，这种事情的复杂度是很高的。

如果把问题简化，就变成了一个在动态规划（一种经典的算法设计方法）学习中的经典例题。

本章从一个简单的投资例子引入问题

给定总投资亮n（整数），和m个单增项目回报函数fk(x): 将x投入到第k个项目中的效益。

把n分成m份，满足，m份的和为n，且m个回报函数值的和最大。

求解这个问题，要用到动态规划算法设计方法。

本章给出了详细求解思路，算法描述、算例分析和算法性质描述。

【作者感受】

本章从一个很有吸引力的问题入手，其实是介绍动态规划。动态规划是算法设计的必学方法，有点难。但是如果一个问题能设计出动态规划算法，而且能实现，其执行效率是很高的。

真的投资比这个复杂的多的多。