投资问题的算法实现

算法实现"/>

投资问题的算法实现

投资问题的算法实现

• • 问题描述
  • 实例
  • 问题建模
  • 算法
  • • 暴力求解
    • • 算法思想
      • 代码
    • 动态规划
    • • 算法思想
      • 代码
    • 输出
    • 总结

问题描述

m元钱，投资 n 个项目。效益函数 f_i (x) 表示第 i 个项目投 x 元的效益( i =1, 2, …, n)。求如何分配每个项目的钱数使得总效益最大？

实例

5 万元，投资给 4 个项目，效益函数：

问题建模

输入：项目总数x；投资金额y；效益函数f_i(k)
输出：最大利润maxProfit

算法

暴力求解

算法思想

对所有项目进行循环，通过限定条件：总投资金额=y，得到所有符合的答案，从中选取最大值，即为所求。

代码

使用C++语言实现：

#include<iostream>
using namespace std;//投资问题的暴力解法
int main(){int profitMatrix[4][6]={0,11,12,13,14,15,   //收益矩阵0,0,5,10,15,20,0,2,10,30,32,40,0,20,21,22,23,24};int x1,x2,x3,x4,x;int sum=0,maxProfit=0;int a[4]={0}; //输出最优向量for(x1=0;x1<6;x1++){for(x2=0;x2<6;x2++){for(x3=0;x3<6;x3++){for(x4=0;x4<6;x4++){x=x1+x2+x3+x4;if(x==5){ //限定条件，投资5万元sum=profitMatrix[0][x1]+profitMatrix[1][x2]+profitMatrix[2][x3]+profitMatrix[3][x4];if(sum>maxProfit){maxProfit=sum;a[0]=x1;a[1]=x2;a[2]=x3;a[3]=x4;}}}}}}cout<<"最大利润为："<<maxProfit<<endl;cout<<"最优投资方案为：( ";for(int i=0;i<4;i++){cout<<a[i]<<" ";}cout<<")";
}

使用Python语言实现：

if __name__ == '__main__':profitMatrix=[[0,11,12,13,14,15],[0,0,5,10,15,20],[0,2,10,30,32,40],[0,20,21,22,23,24]]a=[0,0,0,0] #存放最优投资方案maxProfit=0sumMoney=0for x1 in range(6):for x2 in range(6):for x3 in range(6):for x4 in range(6):x=x1+x2+x3+x4if x==5:sumMoney=profitMatrix[0][x1]+profitMatrix[1][x2]+profitMatrix[2][x3]+profitMatrix[3][x4]if sumMoney>maxProfit:maxProfit=sumMoneya[0]=x1a[1]=x2a[2]=x3a[3]=x4print("最大利润为："+str(maxProfit))print("最优投资方案为："+str(a))

动态规划

算法思想

假设第x个项目投资m万元，则将x个项目的y万元投资问题分解为前x-1个项目投资y-m万元和第x个项目投资m万元。这样就可以将问题规模减小，直至仅有一个项目，此时的最佳投资方案就是其本身。
令outspace[x][y]表示前x个项目投资y万元得到的最大利润，令
profitMatrix[i][m]=f_i(m)，则动态方程为：
outspace[x][y]=profitMatrix[x][m]+outspace[x-1][y-m]
限定边界为outspace[0][k]=profitMatrix[0][k]

代码

使用C++语言实现：

#include<iostream>
using namespace std;int getProfit(int outspace[4][6],int profitMatrix[4][6],int maxProfit){for(int i=0;i<=5;i++){//当仅有一个项目时，此项目的收益即为最优，分开赋值是为了避免下面出现 -1 行outspace[0][i]=profitMatrix[0][i];}for(int i=1;i<4;i++){ //逐次加入第2，3，4个项目for(int j=0;j<=5;j++){//投资金额for(int m=0;m<=j;m++){//m代表最后一个项目投资金额if(outspace[i][j]<profitMatrix[i][m]+outspace[i-1][j-m]){outspace[i][j]=profitMatrix[i][m]+outspace[i-1][j-m];if(outspace[i][j]>maxProfit)maxProfit=outspace[i][j];}}}}return maxProfit;
}
int main()
{int maxProfit = 0;int outspace[4][6]={0};//初始化最大利润矩阵int profitMatrix[4][6]={0,11,12,13,14,15,   //收益矩阵0,0,5,10,15,20,0,2,10,30,32,40,0,20,21,22,23,24};int a=getProfit(outspace,profitMatrix,maxProfit);cout<<"最大收益为："<<a<<endl;return 0;
}

使用Python语言实现：

def getProfit(profitMatrix,outspace,maxProfit):for i in range(6):outspace[0][i]=profitMatrix[0][i]for i in range(1,4):for j in range(6):for m in range(j+1):if outspace[i][j]<profitMatrix[i][m]+outspace[i-1][j-m]:outspace[i][j]=profitMatrix[i][m]+outspace[i-1][j-m]if maxProfit<outspace[i][j]:maxProfit=outspace[i][j]return maxProfitif __name__ =='__main__':profitMatrix=[[0,11,12,13,14,15],[0,0,5,10,15,20],[0,2,10,30,32,40],[0,20,21,22,23,24]]outspace=[]for i in range(4):outspace.append([])for j in range(6):outspace[i].append(0)maxProfit=0a=getProfit(profitMatrix,outspace,maxProfit)print("最大利润为："+str(a))

输出

总结

令m为投资金额，n为项目数
则投资问题的暴力算法时间复杂度为O(mⁿ) 空间复杂度为O(mn）
动态规划算法时间复杂度为O(nm²) 空间复杂度为O(mn)