网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

算法分析与设计——投资问题(动态规划)

2021/6/21 3:10:01 人评论

文章目录一、问题二、解析三、设计四、分析五、代码一、问题 设有m万元,n项投资,函数f(x)表示将x万元投入第i项项目所产生的效益,i1,2,3……,n,问:如何分配这…

文章目录

  • 一、问题
  • 二、解析
  • 三、设计
  • 四、分析
  • 五、代码


一、问题

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

即:目标函数max{f1(x1)+ f2(x2)+…+ fn(xn)},约束条件x1+x2+…+xn=m,x∈N

实例:
在这里插入图片描述

二、解析

设dp[i][t]为前i个项目总共花费t元能得到的最大收益,那么假设分配给第i个项目k元取得了最大收益,则实际上前i-1个项目共得到了j=t-k元,

所以dp[i][t]的最优状态可以由dp[i-1][t-k]+fi(k)中的最优子决策得到,所以对于每个i,t的情况,只要枚举所有dp[i-1][t-k]+fi(k)的状态中最优的即可,得到状态转移方程如下:

dp[i][j + k] = max(dp[i - 1][j] + f[i][k], dp[i][j + k]); 其中j+k=t;

三、设计

在这里插入图片描述

四、分析

时间复杂度 : O(n * m * m)
空间复杂度 : O (n * m)

五、代码

#include<iostream>
#include<vector>
#include<cmath>
#include<time.h>
#include<cstring>
#include<algorithm>
 
using namespace std;

int n, m; // n代表项目的数量 , m代表投资的金额
int f[1000][1000]; // 用户存储给第i个项目投资x万元,能够获得f[i][x]万元的收益
int dp[1000][1000] = {0}; // dp[i][j]表示到第i个项目的时候已经花费了j万元的最大收益

int main()
{    
    scanf("%d %d", &n, &m); 
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            scanf("%d", &f[i][j]); // 对第i个项目投资j万元的收益为f[i][j]
    
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            for (int k = 0; j + k <= m; ++k)
                dp[i][j + k] = max(dp[i - 1][j] + f[i][k], dp[i][j + k]);
    cout << dp[n][m] << endl;
    system("pause");
    return 0;
} 
 
/*
测试案例
4 5
0 11 12 13 14 15
0 0 4 10 15 20
0 2 10 30 32 40
0 20 21 22 23 24
*/

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?