这道题是典型的0-1背包问题。用的背包九讲里面的滚动数组的实现。
| 3624 | Accepted | 224K | 329MS | C++ | 799B |
/*
ID: thestor1
LANG: C++
TASK: poj3624
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>
using namespace std;
int main()
{
int N, M;
scanf("%d%d", &N, &M);
std::vector<int> weights(N);
std::vector<int> desirabilities(N);
for (int i = 0; i < N; ++i)
{
scanf("%d%d", &weights[i], &desirabilities[i]);
}
std::vector<int> DP(M + 1, 0);
for (int i = 0; i < N; ++i)
{
for (int W = M; W >= weights[i]; --W)
{
DP[W] = max(DP[W], DP[W - weights[i]] + desirabilities[i]);
}
}
printf("%d\n", DP[M]);
return 0;
}