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

Sample Output

题目大意:(借鉴别人,非本人所写)

这里写图片描述

解题思路:(借鉴别人,非本人所写)

这里写图片描述

！！第三种方法正解！！

第一种代码:递归(TLE QAQ)

#include<iostream>
#include<cstdio>
using namespace std;
struct Bag{int w,d;
}bag[3500];
int dfs(int n,int m){if(m <= 0)return 0;if(n == 1)return m >= bag[n].w ? bag[n].d : 0;elsereturn m - bag[n].w >= 0 ? max(dfs(n - 1,m - bag[n].w) + bag[n].d,dfs(n - 1,m)) : dfs(n - 1,m);
}
int main(){int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++)scanf("%d%d",&bag[i].w,&bag[i].d);printf("%d\n",dfs(n,m));return 0;
}

第二种方法:动态规划( MLE QAQ)

#include<iostream>
#include<cstdio>
using namespace std;
struct Bag{int w,d;
}bag[3500];
int n,m,dp[3500][13000];
int main(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++)scanf("%d%d",&bag[i].w,&bag[i].d);for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++){if(j < bag[i].w)dp[i][j] = dp[i - 1][j];elsedp[i][j] = max(dp[i - 1][j],dp[i - 1][j - bag[i].w] + bag[i].d);}printf("%d\n",dp[n][m]);return 0;
}

第三种方法: 动态规划 + 滚动数组 (AC)

#include<iostream>
#include<cstdio>
using namespace std;
struct Bag{int w,d;
}bag[3500];
int n,m,dp[13000];
int main(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++)scanf("%d%d",&bag[i].w,&bag[i].d);for(int i = 1;i <= n;i++)for(int j = m;j >= 1;j--)//从大到小,否则数据被覆盖if(j >= bag[i].w)dp[j] = max(dp[j],dp[j - bag[i].w] + bag[i].d);printf("%d\n",dp[m]);return 0;
}