第4

第4

动态规划理论最早被提出来的时候，是用来解决资源的有效分配问题。这一课要介绍的投资问题，有个通用的模式，那就是总资源量有限，要分配给若干个项目，每个项目都有一个投入与收益的关系，最终的问题是求如何规划在不同项目上的投资，使得收益能够最大化。

问题分析

这一类问题有很多，我们找了个典型的例子，即项目投资问题。假设有数量为 M 的资金，计划用于 N 个投资项目，每个项目投入的资金和获得的回报用一张二维表记录，比如 f[i, x] 表示第 i 个项目投入 x 万元时能获取的收益。最后的问题是如何在这 N 个投资项目上分配这 M 万元的资金，使得最后的收益最大化。比如有 600 万元，投资 3 个项目，每个项目的投资收益如下表所示：

显然，投资和收益不是线性等比例关系，否则的话，把钱全投到收益比最高的那个项目上就行了，也没啥好规划的了。这个算法也可以用穷举法，因为 N 不是固定的值，所以穷举时可以考虑用递归的方式实现，但是这一课我们考虑用动态规划法来设计这个算法。

投资 N 个项目，看起来好像是毫无关系的离散事件，但是因为投资的总钱数是固定的，这就使它们有了关系。如果我们换个角度看投资的项目，把所有的投资看作是一个求最优解的操作，把对每个项目的投资看作这个操作的一个阶段，就成功地将其转换成了多阶段决策问题。如果要考虑用动态规划解决这个多阶段决策问题，就需要首先证明每个阶段的决策能满足无后向性的要求