最大化投资回报问题:某人有一定的资金用来购买不同面额的债卷,不同面额债卷的年收益是不同的,求给定资金,年限以及债卷面额、收益的情况下怎样购买才能使此人获得最大投资回报。
程序输入约定:第一行第一列表示资金(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)