Description
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
1 Home Problems Status Contest [xiong_tao] Logout 2 xiong_tao ‘s source code for D 3 Memory: 1952 KB Time: 313 MS 4 Language: G++ Result: Accepted 5 6 1 7 2 8 3 9 4 10 5 11 6 12 7 13 8 14 9 15 10 16 11 17 12 18 13 19 14 20 15 21 16 22 17 23 18 24 19 25 20 26 21 27 28 #include<cstdio> 29 #include<string.h> 30 using namespace std; 31 int dp[400000],w[400000],d[4000]; 32 int n,m; 33 int main() 34 { 35 int i,j; 36 while(scanf("%d%d",&n,&m)!=EOF) 37 { 38 for(i=0;i<n;i++) 39 scanf("%d%d",&w[i],&d[i]); 40 memset(dp,0,sizeof(dp)); 41 for(i=0;i<n;i++) 42 for(j=m;j>=0;j--) 43 if(j>=w[i]) 44 dp[j]=dp[j]>dp[j-w[i]]+d[i]?dp[j]:dp[j-w[i]]+d[i]; 45 printf("%d\n",dp[m]); 46 } 47 return 0; 48 } 49 50 FAQ | About Virtual Judge | Forum | Discuss | Open Source Project 51 All Copyright Reserved ©2010-2012 HUST ACM/ICPC TEAM 52 Anything about the OJ, please ask in the forum, or contact author:Isun 53 Server Time: 2014-07-28 18:43:07
D - Charm Bracelet 背包问题,布布扣,bubuko.com
原文：http://www.cnblogs.com/angledamon/p/3873795.html