首页 > 代码库 > D - Charm Bracelet 背包问题
D - Charm Bracelet 背包问题
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 61 42 63 122 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 410 511 612 713 814 915 1016 1117 1218 1319 1420 1521 1622 1723 1824 1925 2026 2127 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 Project51 All Copyright Reserved ©2010-2012 HUST ACM/ICPC TEAM52 Anything about the OJ, please ask in the forum, or contact author:Isun53 Server Time: 2014-07-28 18:43:07