最大化投资回报问题的实现计算机等级考试

文章作者 100test 发表时间 2010:01:02 07:00:01
来源 100Test.Com百考试题网

　　最大化投资回报问题：某人有一定的资金用来购买不同面额的债卷，不同面额债卷的年收益是不同的，求给定资金，年限以及债卷面额、收益的情况下怎样购买才能使此人获得最大投资回报。

　　程序输入约定：第一行第一列表示资金（1000的倍数）总量，第二列表示投资年限；第二行表示债卷面额总数；从第三行开始每行表示一种债卷，占用两列，前一列表示债卷面额，后一列表示其年收益，如下输入实例，

　　10000 1

　　2

　　4000 400

　　3000 250

　　程序实现如下，注释几乎说明了一切，所以不再另外分析。

　　/// 此数组是算法的关键存储结构，用来存储不同阶段各种债卷

　　/// 组合下对应可获取的最大利息。

　　int saifa[80005].

　　/// 此函数用于计算当前债卷在不同购买额下的最优利息情况，

　　/// 注意此时的利息情况是基于上一次债卷的情况下计算得到的，

　　/// 也就是说当前利息最优是基于上一次利息最优的基础上计算出来的，

　　/// 这也正好体现了动态规划中“最优化原则”：不管前面的策略如何，

　　/// 此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。

　　/*

　　动态规划的求解过程一般都可以用一个最优决策表来描述，

　　对于本程序，以示例输入为例，对于第一年，其最优决策表如下：

　　0 1 2 3　4　5　6　7　8　9　10(*1000)　　-- (1)

　　0 0 0 0　400 400 400 400 800 800 800　　-- (2)

　　0 0 0 250 400 400 500 650 800 900 900　　-- (3)