课程作业7：动态规划方法求解投资决策

1.问题

定义m为可用资金总量，在面对共有n个投资项目的情况下，请描述函数f（x）用于计算将x元资金投向第i个项目所带来的边际收益值（其中i=1,2,…,n）。问题：如何合理分配这m元资金以使各项目总投资收益最大化？

2.解析

首先可以对问题建模：求解max{f1(x1)+f2(x2)+…+fn(xn)},且x1+x2+…+xn=m

针对该问题,我们定义了两个数组：dp[i][j]和cost[i][j]。其中,dp[i][j]表示在投资前i个项目时花费j元所能获得的最大效益,cost[i][j]则表示在第i个项目上的投资金额。由此可得递推公式为\ dp\ [i\ ][\ j\ ]=max(dp\ [i-1\ ][\ j-x\ ]+f(i,x)),其中f(i,x)表示第i个项目投资x元所得的价值。同时,需要设定边界条件：当j=0时,dp[0,j]=0;当i=1时,dp[1,j]=f(1,j).这样,我们便可以通过依次遍历每个项目并累计$m$元的投资总额来求解最终结果.具体案例可见下述分析