1先简单描述一下这类题的通解思路
下面是一道具体的例题
例题： 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。
解：依据题意，是要求 f4(60)
根据思路可以模拟出一下代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 int M; 4 int N; 5 int main() 6 { 7 cout << "请输入工厂的个数和每个工厂所有的可能投资额个数:"<< endl; 8 cin >> M >> N; 9 cout << "请输入国家最大投资额" << endl; 10 int money; 11 cin >> money; 12 int array[M][N];//每个工厂在所有可能投资额下的获取利润 13 int array1[M][N];//在某投资额下前M个工厂可以获取的最大利润 14 int path[M][N];//记录在某总投资额下投资一部分资金给第M个工厂下时获取最大利润时这个部分投资额的数值 15 memset(array,0,sizeof(array)); 16 memset(array1,0,sizeof(array1)); 17 memset(path,0,sizeof(path)); 18 cout << "请依次输入每个工厂在所有可能投资额下的获取利润:"<< endl; 19 for(int i=0;i<M;i++){ 20 cout << "请输入第" << i+1 << "个工厂的所有可能投资额下的获取利润：" << endl; 21 for(int j=0;j<N;j++){ 22 cin >> array[i][j]; 23 } 24 } 25 for(int i=0;i<M;i++){ 26 for(int j=0;j<N;j++){ 27 if(i==0){ 28 array1[i][j]=array[i][j]; 29 if(array[i][j]>path[i][j]){//第一个工厂直接全部分配给自己 30 path[i][j]=j;//全部投资额都给自己 31 } 32 } 33 else{ 34 int maxnum=0; 35 for(int k=0;k<N;k++){ 36 if(j-k>=0){//保证投资给除了自己之外的工厂的投资额不能大于总投资额 37 if(array1[i][j]<array[i][k]+array1[i-1][j-k]){//获取收益最大值时投资给自己的投资额 38 array1[i][j]=array[i][k]+array1[i-1][j-k];//更新 39 path[i][j]=k;//记录投资给自己多少； 40 } 41 42 } 43 else{ 44 break; 45 } 46 47 } 48 } 49 } 50 } 51 cout <<"最大利润为" <<array1[M-1][N-1]<< endl; 52 53 //cout << "每个" << endl; 54 money/=10; 55 for(int i=M-1;i>=0;i--){ 56 cout <<"第"<<i+1<<"个工厂投资额为" <<path[i][money]*10<< endl; 57 money-=path[i][money]; 58 59 } 60 61 }
运行结果如下：
