hihoCoder#1043 完全背包

基本动态规划题+状态压缩

看完提示反倒是不会做了。。

代码：

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