九度教程第101题

		提供组数据：
input：
105 10
12 11
16 16
24 15
7 9
29 24
32 25
5 3
43 32
31 41
1 7
output：
112
C语言源码：
[cpp]  
#include<stdio.h>  
int dp[101][1001];  
typedef struct grass  
{  
    int time;  
    int worth;  
}grass;  
grass g[101];  
int max(int a,int b)  
{  
    return a>b?a:b;  
}  
int main()  
{  
    int t,n,i,j;  
    while(scanf("%d %d",&t,&n)!=EOF)  
    {  
        for(i=1;i<=n;i++)  
            scanf("%d %d",&g[i].time,&g[i].worth);  
        for(i=0;i<=n;i++)  
            for(j=0;j<=t;j++)  
                dp[i][j]=0;  
        for(i=1;i<=n;i++)  
        {  
            for(j=0;j<=t;j++)  
            {  
                if(g[i].time<=j)  
                    dp[i][j]=max(dp[i-1][j-g[i].time]+g[i].worth,dp[i-1][j]);  
                else  
                    dp[i][j]=dp[i-1][j];  
            }  
        }  
        printf("%d\n",dp[n][t]);  
    }  
}  
 
						
		
	

补充：软件开发 , C++ ,

上一个：九度教程第102题
下一个：[算法分析]微分求积：复化梯形、复化辛浦生