首页 > 代码库 > tyvj 1005 采药 0-1背包 优化的一位数组 dp 代码1

tyvj 1005 采药 0-1背包 优化的一位数组 dp 代码1

#include <iostream>
#include <string.h>
using namespace std;
int dp[1005], w[105],v[105],T,M;
int max(int x,int y)
{    return x>y?x:y;   }
void  f( )
{   int i,j;
    for (i=1; i<=M; i++)
        for (j=T;j>=0; j--)
           if (j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
int main()
{   int i;    
    cin>>T>>M;
    for ( i=1; i<=M; i++)  cin>>w[i]>>v[i];
    memset(dp,0,sizeof(dp));
    f( );    
    cout<<dp[T]<<endl;
}