NOIP2005 第三题

<问题分析>

根据草药的不可重复性而作为最外层循环，状态转移方程if(j>=w[i]) s[i][j]=max(s[i-1][j],s[i-1][j-w[i]+v[i]) else s[i][j]=s[i-1][j]

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 
 5 
 6 int main()
 7 {
 8     int t,m,i,j,w[101],v[101],s[101][1001];
 9     scanf("%d %d",&t,&m);
10     for(i=1;i<=m;i++)
11     {
12        scanf("%d %d",&w[i],&v[i]);
13     }
14     memset(s[0],0,sizeof(int)*t);
15     for(i=1;i<=m;i++)
16     {
17        for(j=0;j<=t;j++)
18        {
19           if(j-w[i]<0) s[i][j]=s[i-1][j];
20           else if(s[i-1][j]<s[i-1][j-w[i]]+v[i])
21           {
22              s[i][j]=s[i-1][j-w[i]]+v[i];
23           }
24           else s[i][j]=s[i-1][j];
25        }
26     } 
27     printf("%d
",s[m][t]);
28     while(true);
29     return 0; 
30 }