1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
#include <iostream> #include <algorithm> #include <cstring> using namespace std;
int W, n; int w[105], v[105];
int mem[105][1005]; int dfs(int pos, int rest) { if (mem[pos][rest] != -1) return mem[pos][rest]; if (pos == n + 1) return mem[pos][rest] = 0; int a = 0, b = -1; a = dfs(pos + 1, rest); if (rest >= w[pos]) b = dfs(pos + 1, rest - w[pos]) + v[pos]; return mem[pos][rest] = max(a, b); }
int main() { cin >> W >> n; for (int i = 1; i <= n; i++) cin >> w[i] >> v[i]; memset(mem, -1, sizeof(mem));
cout << dfs(1, W) << endl; return 0; }
|