侯燕.cpp

此程序是关于动态规划算法的描述

#include<iostream.h>
main ()
{int i,j,k,m,n,rest,a[100][100],gain[100];
 float q[100],f[100],temp[100];
 cout<<"有几个项目?"<<endl;
 cout<<"m=";
 cin>>m;
 cout<<"共有多少资金?"<<endl;
 cout<<"n=";
 cin>>n;
 cout<<"Input one item gain table:"<<endl;
 for (j=0;j<=n;j=j+1)
 {cin>>q[j];
  f[j]=q[j];
 }
 for (j=0;j<=n;j=j+1)
	 a[1][j]= j;
 for (k=2;k<=m;k=k+1)
 {cout<<"Input another item gain table"<<endl;
  for (j=0;j<=n;j=j+1)
  {temp[j]=q[j];
   cin>>q[j];
   a[k][j]=0;
  }
  for (j=0;j<=n;j=j+1)
	  for(i=0;i<=j;i=i+1)
		  if(f[j-i]+q[i]>temp[j])
		  {temp[j]=f[j-i]+q[i];
		   a[k][j]=i;
		  }
		  for(j=0;j<=n;j=j+1)
			  f[j]=temp[j];

}
 rest = n;
 for (i=m;i>=1;i=i-1)
 {gain[i]=a[i][rest];
 rest=rest-gain[i];
 }
 for(i=1;i<=m;i=i+1)
	 cout<<gain[i]<<" ";
     cout<<f[n]<<endl;
	 
}