NOIP2006 第二题

<问题分析>

0/1背包问题，状态转移方程 if(j-w[i]>=0) s[i][j]=max(s[i-1][j],s[i-1][j-w[i]]+w[i]*v[i]) else s[i][j]=s[i-1][j]

可能有超内存的问题，实际上只需要两个转移的状态就可以了。

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