算法分析与设计(work7)

1、问题

设m万元钱，n项投资，函数 fi (x)表示将x万元投入第i项项目所产生的效益，i=1,2,...,n.问:如何分配这 m 元钱，使得投资的总效益最高?

2、解析

设 (dp[i][j]) 表示用(j)万元投入到前(i)个项目中可以获取的最大收益。

很显然，首先考虑转移方程，对于前(i)个项目的最大收益一定是从前(i-1)个项目的最大收益转化而来。那么可以枚举第(i)个项目所投资金额，设其为(x)，那么其收益就是(f_{i}(x))，那么我们就可以推出转移方程 (dp[i][j]=dp[i-1][j-x]+f_{i}(x)(x<=j))。

方程不断转移最后 (dp[n][m]) 即是最大收益。

3、设计

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        for(int k=j;k>=1;k--){
            dp[i][j]=max(dp[i][j],dp[i-1][j-k]+f[i][k]);
        }
    }
}

4、分析

需要枚举所有用(j)万元投入到前(i)个项目中的状态，时间复杂度(O(nm))，对于每个状态下，我们需要枚举第(i)个项目的投资数量进行转移，时间复杂度(O(m))，因此，总时间复杂度(O(nm^2))。

5、源码

github源码地址：
https://github.com/HaHe-a/Algorithm-analysis-and-design-code/blob/master/Investment issues.cpp