hihoCoder#1038 01背包

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int main() {
 6     int N, M;
 7     int score[100010];
 8     int need[512];
 9     int value[512];
10 
11     cin >> N >> M;
12 
13     for (int i = 0; i < N; i++)
14         cin >> need[i] >> value[i];
15 
16     for (int i = 0; i <= M; i++)
17         score[i] = 0;
18 
19     for (int i = 0; i < N; i++)
20         for (int j = M; j >= need[i]; j--)
21             score[j] = max(score[j], value[i] + score[j - need[i]]);
22 
23     cout << score[M] << endl;
24 
25     return 0;
26 }