guihua.h

算法设计分析

#include "iostream.h"
void main()
{
	int i,j,k,m,n,rest,a[100][100],gain[100];
	float q[100],f[100],temp[100];
	cout<<"how many item?  ";
	cin>>m;
	cout<<"how many money?  ";
	cin>>n;
	cout<<"input one item gain table: ";
	for(j=0;j<=n;j++)
		{
			cin>>q[j];
			f[j]=q[j];
		}
	for(j=0;j<=n;j++)
		a[1][j]=j;
	for(k=2;k<=m;k++)
		{
			cout<<"input another item table: ";
			for(j=0;j<=n;j++)
				{
					temp[j]=q[j];
					cin>>q[j];
					a[k][j]=0;
				}
			for(j=0;j<=n;j++)
				for(i=0;i<=j;i++)
					if(f[j-1]+q[i]>temp[j])
						{
							temp[j]=f[j-1]+q[i];
							a[k][j]=i;
						}
					for(j=0;j<=n;j++)
						f[j]=temp[j];
	}
	rest=n;
	for(i=m;i>=1;i--)
		{
			gain[i]=a[i][rest];
			rest=rest-gain[i];
		}
	for(i=1;i<=m;i++)
		cout<<gain[i];
		cout<<f[n];
}