Invest

#include<iostream>
using namespace std;
const int money = 8;
const int num = 4;
//投资收益函数
int f[num][money]={0, 0, 0, 0, 0, 0, 0, 0,
             0, 11, 13, 15, 21, 24, 30, 35,
             0, 12, 16, 21, 23, 25, 24, 34,
             0, 8, 12, 20, 24, 26, 30, 35};
int F[num][money], s[num][money];
int main(){
    //初始化边界值
    for(int i=0; i<money; i++){
        F[1][i] = f[1][i];
        s[1][i] = i;
        F[0][i] = 0;
        s[0][i] = 0;
    }
    for(int i=0; i<num; i++){
        F[i][0] = 0;
        s[i][0] = 0;
    }
    //迭代求解
    for(int i=1; i<num; i++){
        for(int j=1; j<money; j++){
            F[i][j] = F[i-1][j];
            //进行k次迭代找到最大收益
            for(int k=0; k<j; k++){
                //发现更大的收益的时候进行更新
                if(F[i-1][k] + f[i][j-k] > F[i][j]){
                    F[i][j] = F[i-1][k] + f[i][j-k];
                    s[i][j] = j-k;
                    //s[i][j]记录F[i][j]得到最大收益时分配给第i个项目多少钱
                }
            }
        }
    }//时间复杂度O(n*m^2) n是项目个数 m是钱的数量
    cout<<F[num-1][money-1]<<endl;
    return 0;
}