最大化投资回报问题的实现

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

    程序输入约定：第一行第一列表示资金（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

    {

    memset(saifa,0,sizeof(saifa));

    scanf("%d%d",&money,&year);

    scanf("%d",&d);

    for(i=0;i

    {

    scanf("%d%d",&pay,&bond);

    add(pay/1000,bond);

    }

    // 计算指定年限内最优组合的本金利息总额

    for(i=0;i

    { cout << saifa[money/1000] << " "; // for debug

    money += saifa[money/1000];

    }

    cout << endl; // for debug

    printf("%d\n",money);

    }

    return 0;

    }