题解 | dp问题

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

#define fas(i,a,b) for(int i=a;i<b;++i) //[)
#define fdes(i,b,a) for(int i=b;a<=i;--i) //[]
#define mm memset

const int MAXN=100;
const int MAXC=1000;
int dp[MAXC+1];
int v[MAXN];
int w[MAXN];
int main() 
{
    int c,n;
    while (cin >> c>>n) 
    { 
        fas(i,0,n)
            cin>>w[i]>>v[i];
        mm(dp,0,(MAXC+1)*sizeof(int));
        fas(i,0,n)
        {
            fdes(j,MAXC,0)
            {
                if(w[i]<=j)
                {
                    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
                }
            }
        }
        cout<<dp[c]<<endl;   
        
    }
}
// 64 位输出请用 printf("%lld")