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];elsea = 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; }

?

總結(jié)

以上是生活随笔為你收集整理的Charm Bracelet的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。