动态规划之投资策略规划 - z84616995z的专栏 - 博客频道 - CSDN.NET
你所掌握的算法知识帮助你从Acme计算机公司获得了一份令人兴奋的工作，签约奖金1万美元。你决定利用这笔钱进行投资，目标是10年后获得最大回报。你决定请Amalgamated投资公司管理你的投资，该公司的投资回报规则如下。该公司提供n种不同的投资，从1~n编号。在第j年年底，比你会得到drij美元。回报率是有保证的，即未来10年每种投资的回报率均已知。你每年只能做出一次投资决定。在每年年底，你既可以将钱继续投入到上一年选择的投资种类中，也可以转移到其他投资中(转移到已有的投资种类，或者新的投资种类)。如果跨年时你不做投资转移，需要支付f1美元的费用，否则，需要支付f2美元的费用，其中f2>f1。
a。如上所述，本问题允许你每年将钱投入到多种投资中。证明：存在最优投资策略，每年都将所有钱投入到单一投资中(脊柱最优投资策略只需最大化10年的回报，无需关心任何其他目标，如最小化风险)。
b.证明：规划最优投资策略问题具有最优子结构性质。
c.设计最优投资策略规划算法，分析算法时间复杂度。
d. 假定Amalgamated投资公司在上述规则上又加入了新的限制条款，在任何时刻你都不能在任何单一投资种类中投入15000美元以上。证明：最大化10年回报问题不再具有最优子结构性质。
分析与解答：正如a题所言，如果每年都将所有钱投入到单一投资中，存在最优投资策略。一共n年m种投资，每年都有m种方式选择，持续n年，那么一共有m^n种可能的选择方式，但是这指数种选择方式中存在很多重叠子结构，实际上除去重叠的，只有n*m²种子结构。该问题在第j年寻找获得收益最大时所选择的位置将会产生新的子问题，要想求第j年最佳选择，那么需要求第j-1年最佳选择，根据第j-1年最优解来求第j年最优解。假定已经知道第j-1年之前的最佳选择方式，第j-1年每种投资都已经得到最大收益，那么我们只需在第j-1年的这m种投资中结合第j年的每种投资方式选择一种获利最大的方式。利用剪贴法证明第j年最佳投资方式必然包含第j-1年最佳投资方式。假定有比第j-1年每种投资获利更大的获利方式，那么把此方式"剪贴"上去，从而得到一个第j年获利更大方式.，那么与最初的第j年最佳投资方式矛盾。假定共n年m种投资，那么运行时间是O(n*m*m).
Read full article from 动态规划之投资策略规划 - z84616995z的专栏 - 博客频道 - CSDN.NET
