约束条件动态规划.cpp

这里面是很多经典算法的源代码

#include<stdio.h>

double g[3][8]={
					{0,0.11,0.13,0.15,0.21,0.24,0.30,0.35},
					{0,0.12,0.16,0.21,0.23,0.25,0.24,0.34},
					{0,0.08,0.12,0.20,0.24,0.26,0.30,0.35}
				};

double dp[3][8];
int i,j;
double max(double* p,int n)
{
	double max;
	max=p[0];
	for(int i=1;i<n;i++)
	{
		if(p[i]>max)
		{
			max=p[i];
		}
	}
	return max;
}

double answer(int m,int n)
{
	double a[8];
	int k;
	for(k=0;k<8;k++)
	{
		a[k]=0;
	}	
	
	if(dp[m][n]!=-1)
	{
		return dp[m][n];
	}
	if(n==0)
	{
		for(i=m;i>=0;i--)
			dp[i][n]=0;
		return dp[m][n];
	}
	if(m==0)
	{
		dp[m][n]=g[m][n];
		return dp[m][n];
	}
	else 
	{
	
		for( k=0;k<=n;k++)
		{
			a[k]=answer(m-1,n-k)+g[m][k];
		}
		dp[m][n]=max(a,8);
		return dp[m][n];
	}
}
main()
{
	for(i=0;i<3;i++)
		for(j=0;j<8;j++)
		{
			dp[i][j]=-1;
		}
	double max=answer(2,7);
	printf("%f",max);
	return 0;
}