Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 15375 | Accepted: 7013 |
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 此题用二维数组很可能超内存,需要用一维数组求解,因为定义个全局变量n有在主函数里面定义个局部变量n,以为是逻辑错误,调试了近两个小时。。。 其实这个程序w[i]和v[i]数组都可以用两个变量代替,详见刘汝佳算法经典入门。。。//date 2013.4.9 POJ 3624 Accepted 300K 282MS C++ 897B #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 3500; const int maxm = 13000; int w[maxn], v[maxn]; int f[maxm];//数组开小runtime error! int weight; int n; using namespace std; void DP() { for(int i = 1; i <= n; i++) { for(int j = weight; j >= w[i]; j--) { f[j] = max(f[j], f[j-w[i]]+v[i]); } } } void init() { memset(f, 0, sizeof(f)); memset(v, 0, sizeof(v)); memset(w, 0, sizeof(w)); } int main() { //int n; 注意局部变量可以隐藏全局变量,一个多小时的代价! while(scanf("%d%d", &n, &weight) != EOF) { for(int i = 1; i <= n; i++) { cin >> w[i]; cin >> v[i]; } DP(); cout << f[weight] << endl; init(); } return 0; } /********************* TEST: 4 6 1 4 2 6 3 12 2 7 ****************/