POJ3624 Charm Bracelet(01背包問題）

題目就不寫了，太經典了

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 3500
int w[N],d[N];
int dp[12880];
int main()
{
  int i,j,n,m;
  cin>>n>>m;
    memset(w,0,sizeof(w));
    memset(d,0,sizeof(d));
    
   for(i=1;i<=n;i++)
    cin>>w[i]>>d[i];
    
   memset(dp,0,sizeof(dp)); 
      for(i=1;i<=n;i++)
       for(j=m;j>=w[i];j--)
      {
        if(dp[j-w[i]]+d[i]>dp[j])
       dp[j]=max(dp[j-1],dp[j-w[i]]+d[i]);
    } 
  cout<<dp[m]<<endl;
  return 0;
}