最大化投资回报问题的实现
做IT就要做精英,至少4000/月吧?
JAVAV工程师权威认证 [上海央邦]学一送一,超值! 【安博亚威】CCIE考试通过率第一! 定向委培RHCA,通过考试年薪10W Windows高级工程师的培训地 最大化投资回报问题:某人有一定的资金用来购买不同面额的债卷,不同面额债卷的年收益是不同的,求给定资金,年限以及债卷面额、收益的情况下怎样购买才能使此人获得最大投资回报。 程序输入约定:第一行第一列表示资金(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) (1) -- 表示首先选利息为400的债卷在对应资金下的最优利息。 (2) -- 表示可用来购买债卷的资金。 (3) -- 表示在已有状态下再选择利息为300的债卷在对应资金下的最优利息。 注意上面表格,在求购买利息为300的债卷获得的最优收益的时候, 参考了以前的最优状态,以3行8列的650为例,7(*1000)可以 在以前购买了0张4000的债卷的基础上再2张3000的,也可以在以前购 买了1张4000的基础上再买1张3000,经比较取其收益大的,这就是典 型的动态规划中的当前最优状态计算。 本程序中把上面的最优决策二维表用一个一维数组表示,值得借鉴。 */ void add(int a,int b) { cout << a << " " << b << endl; // for debug for(int i=0;i<=80000;i++) { if(i+a > 80000) { break; } if(saifa[i]+b > saifa[i+a]) // 累计同时购买多种债卷时的利息 { saifa[i+a] = saifa[i] + b; } if(i<200) // for debug cout << i << "-" << saifa[i] << " "; } cout << endl; // for debug } int main(void) { int n,d,money,year,pay,bond; int ii,i; scanf("%d",&n); for(ii=0;ii<n;ii++) { memset(saifa,0,sizeof(saifa)); scanf("%d%d",&money,&year); scanf("%d",&d); for(i=0;i<d;i++) { scanf("%d%d",&pay,&bond); add(pay/1000,bond); } // 计算指定年限内最优组合的本金利息总额 for(i=0;i<year;i++) { cout << saifa[money/1000] << " "; // for debug money += saifa[money/1000]; } cout << endl; // for debug printf("%d\n",money); } return 0; } |
|