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

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

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