POJ 3624

这道题算是01背包问题吧,刚开始做DP的题目，那这一题试试也很不错

hand[j]=max(hand[j],hand[j-w[i]]+d[i]);

#include <iostream>
#include <string.h>
using namespace std;
int hand[12900];
int w[3410],d[3410];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>d[i];
    }
    memset(hand,0,sizeof(hand));
    for(int i=1;i<=n;i++){
        for(int j=m;j>=w[i];j--){
            if((hand[j-w[i]]+d[i])>hand[j]){
                hand[j]=hand[j-w[i]]+d[i];
            }
        }
    }
    cout<<hand[m]<<endl;
    return 0;
}