投资问题算法

解决投资问题的不同算法
2. 1 利用蛮力法求解投资问题
用蛮力法解决投资问题, 需要考虑给定n 个投资项目集合的所有子集, 找出所有可能的子集( 总投资
43
玉溪师范学院学报( 第26卷) 2010 年第8 期Journal of Yuxi Normal University Vol. 26 No. 8 Aug. 2010
额不超过可用资金总数M 的子集) , 计算每个子集的总利润, 然后在他们中找到利润最大的子集.
根据以上分析, 利用蛮力法求解投资问题算法伪代码如下:
bestv 是算法当前获得最优效益值.
( 1) 采用生成子集算法生成n 个投资项目集合的所有子集;
( 2) fo r( i = 0; i < 2n; i + + )
∀计算第i 个子集所对应项目的总投资额m
# if (m < = M)
( a) 计算第i 个子集的总利润v
( b) if ( bestv < = v)
( c) bestv = v ;
∃否则该子集为不可行子集
对于一个具有n 个元素的集合, 其子集数量是2n
, 所以, 不论生成子集的算法效率有多高, 蛮力法都会
导致一个( 2n ) 的算法.
2. 2 利用动态规划法求解投资问题
利用动态规划法的设计思想, 投资问题可以看作是决策一个序列( x 1 , x 2 , !, x n ) , 对任一变量x i 的决
策是决定x i = 1 还是x i = 0. 在对x i- 1 决策后, 已确定了( x 1 , !, x i- 1 ) , 在决策x i 时, 有两种情况: ( 1) 资金
不足以投资项目i, 则x i = 0, 利润不增加; ( 2) 资金足够投资项目i ,
则x i = 1, 利润增加了vi .
首先证明投资问题满足最优性原理.
设( x 1 , x 2 , !, x n ) 是所给投资问题的一个最优解, 则( x 2 , !, x n ) 是下面一个子问题的最优解:
n
i= 2
six i M- s1x 1
x i { 0, 1} ( 2 i n)
max n
i= 2
v ix i
如若不然, 设( y 2 , !, y n ) 是上述子问题的一个最优解, 则
因此, n
i= 2
viy i > n
i = 2
v ix i , 且s1x 1 + n
i= 2
siy i M
可得到: v1 x 1 + n
i= 2
viy i > v1 x 1 + n
i= 2
vix i = n
i= 1
vix i
这说明( x 1 , y 2 , !, y n ) 是所给投资问题比( x 1 , x 2 , !, x n ) 更优的解, 从而导致矛盾.
令d( i , j ) 表示使用投资资金j ( 1 j M) 投资前i( 1 i n) 个项目的利润最大值. 如果资金不足
以投资项目i, 则投资前i 个项目得到的最大利润和投资前i - 1 个项目得到的最大利润是相同的, 即项目
i 不能被投资; 如果资金足够投资项目i, 则会有以下两种情况: ( 1) 如果投资第i 个项目, 则投资项目的利
润等于使用投资资金j - si 投资前i - 1 个项目的利润加上第i 个项目的利润v i , 即d( i - 1, j - si ) + vi ;
( 2) 如果第i 个项目没有被投资, 则投资资金的利润就等于使用投资资金j 投__________资前i 个项目的利润. 显然,
取二者中利润较大者作为使用投资资金j 投资前i 个项目的利润的最优解. 这样我们可以得到如下动态规
划函数:
d ( i, j ) =
d ( i - 1, j ) 0 j < si
max{ d ( i - 1, j ) , d( i- 1, j - si ) + vi } 1j si
( 3)
根据以上分析, 利用动态规划法求解投资问题算法伪代码如下:
( 1) 初始化数组d[ n + 1] [ M+ 1] 的第0 行和第0 列为0.
44
玉溪师范学院学报
( 2) 决策项目i 是否被投资.
for( i = 1; i < = n; i+ + ) / / 计算第i 行, 进行第i 次迭代
for( j = 1; j < = M; j + + )
if( j < s[ i ] ) / / 资金不足以投资项目i
d[ i ] [ j ] = d[ i - 1] [ j ] ;
else / / 资金足够投资项目i
d[ i] [ j ] = max ( d[ i - 1] [ j ] , d[ i- 1] [ j - s[ i] ] + v[ i] ) ;
( 3) 对变量x i 的决策: 决定x i = 1 还是x i = 0.
j = M; / / 求项目的投资情况
for ( i = n; i > 0; i- - )
{
if( d[ i ] [ j ] > d[ i - 1] [ j ] ) { / / 项目i 被投资
x [ i ] = 1;
j = j - s[ i ] ;
}
elsex [ i] = 0; / / 项目i 没有被投资
}
( 4) 返回项目投资的最大利润d[ n] [ M] .
上述算法中第2 步的两层嵌套的for 循环, 其时间性能是O( n % C) , 第3 步的for 循环的时间性能是
O( n) , 所以, 算法的时间复杂性为O( n % C) .
2. 3 利用贪心法求解投资问题
利用贪心法求解投资问题时, 贪心策略是选择单位资金利润最大( 用投资该项目的利润/ 投资该项目
的资金) 项目, 在利润增长和资金消耗两者之间寻找平衡. 即每次从项目集合中选择单位资金利润最大的
项目, 如果其投资额小于可用的投资资金, 就可以对其进行投资, 并将可用的投资资金减去该项目的投资
额, 然后我们就面临了一个最优子问题& & & 它同样是投资问题, 只不过可利用的投资资金减少了, 投资项
目减少了. 因此投资问题具有最优子结构性质.
根据以上分析, 利用贪心法求解投资问题算法伪代码如下:
( 1) 改变数组s 和v 的排列顺序, 使其按单位资金利润v[ i ] / s[ i ] 降序排列;
( 2) 将数组x [ n] 初始化为0; / / 初始化解向量
( 3) i = 1;
( 4) 循环, 直到( s[ i] > M) {
∀x [ i] = 1; / / 将投资第i 个项目
# M = M- s[ i ] ;
∃i+ + ; v
}
该算法的时间主要消耗在将各种项目依其单位资金的利润从大到小排序. 因此, 其时间复杂性为
O( nlog2n) .
45
安镇宙刀学龙: 投资问题的算法分析
3 不同算法的比较分析
通过以上对投资问题的求解分析, 我们可以看到各种算法设计方法有各自不同的特点, 有各自不同的
效率. 对于求解投资问题, 各算法的时间复杂度及优缺点比较如以下附表所示:
附表各算法的时间复杂度及优缺点比较表
算法时间复杂度优点缺点
蛮力法O( 2n ) 直观, 好理解
时间复杂度高, 且其时
间下界为( 2n )
动态规划法O( nC)
把一个多维决策问题转化为若干个一维最优化问题, 能求出全局极大或极小空间占据过多
贪心法O( nlog 2 n) 速度较快
局部最优选择, 并不总
能获得整体最优解。