Advertisement
ambition-xx

Invest

Nov 12th, 2020 (edited)
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.01 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. const int money = 8;
  4. const int num = 4;
  5. //投资收益函数
  6. int f[num][money]={0, 0, 0, 0, 0, 0, 0, 0,
  7.              0, 11, 13, 15, 21, 24, 30, 35,
  8.              0, 12, 16, 21, 23, 25, 24, 34,
  9.              0, 8, 12, 20, 24, 26, 30, 35};
  10. int F[num][money], s[num][money];
  11. int main(){
  12.     //初始化边界值
  13.     for(int i=0; i<money; i++){
  14.         F[1][i] = f[1][i];
  15.         s[1][i] = i;
  16.         F[0][i] = 0;
  17.         s[0][i] = 0;
  18.     }
  19.     for(int i=0; i<num; i++){
  20.         F[i][0] = 0;
  21.         s[i][0] = 0;
  22.     }
  23.     //迭代求解
  24.     for(int i=1; i<num; i++){
  25.         for(int j=1; j<money; j++){
  26.             F[i][j] = F[i-1][j];
  27.             //进行k次迭代找到最大收益
  28.             for(int k=0; k<j; k++){
  29.                 //发现更大的收益的时候进行更新
  30.                 if(F[i-1][k] + f[i][j-k] > F[i][j]){
  31.                     F[i][j] = F[i-1][k] + f[i][j-k];
  32.                     s[i][j] = j-k;
  33.                     //s[i][j]记录F[i][j]得到最大收益时分配给第i个项目多少钱
  34.                 }
  35.             }
  36.         }
  37.     }//时间复杂度O(n*m^2) n是项目个数 m是钱的数量
  38.     cout<<F[num-1][money-1]<<endl;
  39.     return 0;
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement