guihua.cpp

动态规划的投资问题

#include <stdio.h>

int istar[10];

float dp_invest(int N,int K){
 int i,j,sum,z,d[10][50];
 float g[10][50],f[10][50];
 printf(" The return function values as follows! ");
 for(j=0;j<K+1;j++)
  printf(" %d",j);
 for(i=0;i<N;i++)
  {printf(" task%d: ",i+1);
  for(j=0;j<K+1;j++)
   scanf("%f",&g[i][j]);
  }
 for(i=0;i<N;i++)
  for(j=0;j<K+1;j++)
   {f[i][j]=0;d[i][j]=0;}
 for(j=0;j<K+1;j++)
  {f[N-1][j]=g[N-1][j];
   d[N-1][j]=j;
   }
 for(i=N-2;i>=0;i--)
  for(j=1;j<K+1;j++)
   {f[i][j]=g[i][0]+f[i+1][j];
   d[i][j]=0;
   for(z=1;z<=j;z++)
    if((g[i][z]+f[i+1][j-z])>f[i][j])
     {f[i][j]=g[i][z]+f[i+1][j-z];
     d[i][j]=z;
     }
   }
 istar[0]=d[0][K];
 for(i=1;i<N;i++)
  {sum=0;
  for(j=0;j<=i-1;j++)
   sum=sum+istar[j];
  istar[i]=d[i][K-sum];
   }
 return f[0][K];
}

void main(){
 int i,N,K;
 clrscr();
 printf("WELCOME TO THE DYNAMIC_INVEST SYSTEM! ");
 printf("How many tasks ?    ");
 scanf("%d",&N);
 printf(" How many units of materials ?    ");
 scanf("%d",&K);
 printf(" The optimal return is            %f",dp_invest(N,K));
 for(i=0;i<N;i++)
  printf(" The optimal amout to invest in task %d  is      %d",i+1,istar[i]);
 getch();
}