poj3624 Charm Bracelet

 /* 题目：吊饰手链 * 题意：贝西去购物中心的珠宝店看见一个吊饰手链。当然，贝西想用从N(1 <= N <= 3402)个饰品中选出一些填充手链使手链达到最好的状态。 * 在提供的列表里，每个饰品都有一个重量Wi(1 <= Wi <= 400)和一个期望因子Di(1 <= Di <= 100)。每个饰品只能被使用一次。贝西可以提供 * 一条权重不能超过M(1 <= M << 12880)的手链。 * 给出手链的重量限制以作为约束，还有给出饰品的重量和期望列表。计算出手链可能的最大期望和。 * 思路：就是普通的01背包，dp公式：dp[j] = max(dp[j], dp[j - W[i]] + D[i]) **/ #include<stdio.h> #include<string.h> const int MAXN = 4000; const int MAXM = 13000; int dp[MAXM], W[MAXN], D[MAXN]; int main() { int N, M; scanf("%d%d", &N, &M); for(int i = 1; i <= N; i++) { scanf("%d%d", &W[i], &D[i]); } memset(dp, 0, sizeof(dp)); for(int i = 1; i <= N; i++) for(int j = M; j >= W[i]; j--) { int tmp = dp[j - W[i]] + D[i]; if(tmp > dp[j]) dp[j] = tmp; } printf("%d\n", dp[M]); return 0; }