| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 29295 | Accepted: 13143 |
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
Source
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int max(int a,int b) 6 { 7 return a>b?a:b; 8 } 9 int main() 10 { 11 int n,m,i,j; 12 int a[5000],b[5000]; 13 while(~scanf("%d%d",&n,&m)) 14 { 15 for(i=0; i<n; i++) 16 scanf("%d%d",&a[i],&b[i]); 17 int dp[13000]; //dp数组的大小wa了一次，要注意必须和最大重量相同，而不是最大珠子个数 18 memset(dp,0,sizeof(dp)); 19 for(i=0; i<n; i++) 20 for(j=m; j>=a[i]; j--) 21 dp[j]=max(dp[j],dp[j-a[i]]+b[i]); //比较加上这颗珠子和不加的价值谁更大，记录大的那个 22 printf("%d\n",dp[m]); 23 } 24 return 0; 25 }
原文：http://www.cnblogs.com/pshw/p/5003441.html