投资问题（动态规划）

#include <iostream>
#define M 5//总钱数M万
#define N 4//总项目数N
using namespace std;
//收益函数：一共四个项目，每个项目下标为投入钱数，数组值为取得的收益
int f[N][M + 1] = {
    {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 mem[M][N];//备忘录
int d[M][N];//记录与分配相关，eg：d[4][3]记录的是5万元分配给前4个项目时，第四个项目分配了多少钱
int Invest_Promble(int m, int n)//用不超过m元钱投资前n个项目
{
    int i, F, temp0, temp1;
    temp0 = mem[m - 1][n - 1];
    if(temp0 != 0){
        return temp0;
    }
    else{
        F = f[n - 1][m];
        if(n == 1) d[m - 1][n - 1] = m;
        else{
            for(i = m - 1; i >= 0; --i){
                temp1 = f[n - 1][i] + Invest_Promble(m - i, n - 1);
                if(temp1 > F){
                    F = temp1;
                    d[m - 1][n - 1] = i;
                }
            }
        }
        mem[m - 1][n - 1] = F;
        //cout<<m<<" "<<n<<" "<<F<<endl;
        return F;
    }
}
void Distribution(int m, int n)
{
    if(n == 0) return;
    int temp = d[m - 1][n - 1];
    cout<<"项目"<<n<<"投入："<<temp<<"万元"<<endl;
    Distribution(m -= temp, --n);
} 
int main()
{
    cout<<"最大收益："<<Invest_Promble(M, N)<<"万元"<<endl;
    Distribution(M, N);
    return 0;
}

原理参见 屈婉玲老师 算法设计与分析 ORZ