P1048 采药

admin

标准的二维数组的DP

1. #include<iostream>
   
2. using namespace std;
   
3. const int mm=110;
   
4. const int mn=1100;
   
5. int W,N;
   
6. int w[mm],v[mm];
   
7. int f[mn][mm];
   
8. int i,j,k;
   
9. int  main()
   
10. {
    
11.         cin>>W>>N;
    
12.         for (i=1; i<=N; i++)  cin>>w[i]>>v[i];
    
13.         for (k=1; k<=N; k++)
    
14.                 for (int n=0; n<=W; n++)
    
15.                         if (n<w[k])f[n][k]=f[n][k-1];
    
16.                         else
    
17.                                 f[n][k]=max(f[n][k-1],f[n-w[k]][k-1]+v[k]);
    
18.         cout<<f[W][N];
    
19.         return 0;
    
20. }

复制代码