Charm Bracelet

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di

Output

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

4 6
1 4
2 6
3 12
2 7

Sample Output

23

C++版本一 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;
int n,m;
struct node{
    int d,w;

}b[4000];
bool cmp(node a,node b){
    if(a.w==b.w)
        return a.d>a.d;
    return a.w>b.w;

}
int dp[13005];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d%d",&b[i].w,&b[i].d);
    }
    memset(dp,0,sizeof(dp));
    sort(b,b+n,cmp);
    for(int i=0;i<n;i++){
        //dp[i]=b[i].d;
        for(int j=m;j>=b[i].w;j--){
            dp[j]=max(dp[j],dp[j-b[i].w]+b[i].d);
        }
    }
    cout << dp[m] << endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

///2014.4.10
///poj3624
 
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
int N,M;
int w[3500],c[3500];
int f[13500];
 
int main()
{
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);
 
    cin>>N>>M;
    for(int i=1 ; i<=N ; i++){
        cin>>c[i]>>w[i];
    }
    memset(f,0,sizeof(f) );
    for(int i=1 ; i<=N ; i++){
        for(int j=M ; j>=1 ; j--){
            int a;
            if( j-c[i]>=0 )
                a = f[j-c[i]]+w[i];
            else
                a = 0;
            f[j] = f[j]>a? f[j]:a;
        }
    }
    cout<<f[M]<<endl;
    return 0;
}

C++版本三

#include <iostream>  
using namespace std;  
  
const int MAX_N = 3405;  
const int MAX_M = 12885;  
  
int dp[MAX_M];  
int w[MAX_N];  
int d[MAX_N];  
  
int max(int a, int b) {  
    return a > b ? a : b;  
}  
  
int main()  
{  
    int n, m;  
    cin >> n >> m;  
  
    for(int i = 1; i <= n; i++) {  
        cin >> w >> d;  
    }  
  
    for(int i = 1; i <= n; i++) {  
        for(int j = m; j >= w; j--) {  
            dp[j] = max(dp[j-w] + d, dp[j]);  
        }  
    }  
  
    cout << dp[m] << endl;  
  
    return 0;  
}