p1025.cpp

vijos动态规划5题:P1002,P1006,P1011,P1014,P1025

#include <cstdlib>
#include <iostream>

using namespace std;

int m,n,w[1001]={0},c[1001]={0};
long f[1001][1001]={0};

int max(int x,int y)
{
    if(x>y)return x;else return y;
}

int main(int argc, char *argv[])
{
    cin>>n>>m;
    int i,j;
    for(i=1;i<=n;i++)
     cin>>c[i]>>w[i];
    for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
     {
            if(j>=w[i])f[i][j]=max(f[i-1][j-w[i]]+c[i],f[i-1][j]);
            else f[i][j]=f[i-1][j];
     }
    cout<<f[n][m]<<endl;
    return 0;
}