1. #include <iostream>
    2. #include <functional>
    3. #include <numeric>
    4. #include <algorithm>
    5. using namespace std;
    7. class Solver1 {
    8. /*
    9. f[i][j] 表示 只看前 i 个物品，背包大小为 j 时的最大价值
    10. result = max(f[n][0-v])
    11. f[i][j]:
    12.     1. 不选 i ，f[i][j] = f[i - 1][j]
    13.     2. 选 i ，f[i][j] = f[i - 1][j - w[i]] + v[i]
    14. f[0][0] = 0
    15. */
    16.     const static int MAXN = 1000 + 5;
    17.     int dp[MAXN][MAXN];
    18.     int w[MAXN], v[MAXN];
    20. public:
    21.     void f() {
    22.         int N, V;
    23.         cin >> N >> V;
    24.         for (int i = 1; i <= N; i++)
    25.             cin >> v[i] >> w[i];
    27.         for (int i = 1; i <= N; i++)
    28.             for (int j = 0; j <= V; j++) {
    29.                 dp[i][j] = dp[i - 1][j];
    30.                 if (j >= v[i])
    31.                     dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
    32.             }
    33.         cout << dp[N][V] << endl;
    34.     }
    35. };
    37. class Solver2 {
    38.     /*
    39.     一维优化
    40.     */
    41.     static const int MAXN = 1000 + 5;
    43.     int v[MAXN], w[MAXN];
    44.     int dp[MAXN] = {};
    46. public:
    47.     void f() {
    48.         int N, V;
    49.         cin >> N >> V;
    50.         for (int i = 1; i <= N; i++)
    51.             cin >> v[i] >> w[i];
    53.         for (int i = 1; i <= N; i++)
    54.             for (int j = V; j >= v[i]; j--)
    55.                 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    57.         cout << dp[V] << endl;
    58.     }
    59. };
    61. class Solver3 {
    62.     static const int MAXN = 1000 + 5;
    63.     static const int INF = 0x3f3f3f3f;
    65.     int v[MAXN], w[MAXN];
    66.     int dp[MAXN];
    68. public:
    69.     void f() {
    70.         int N, V;
    71.         cin >> N >> V;
    72.         for (int i = 1; i <= N; i++)
    73.             cin >> v[i] >> w[i];
    75.         dp[0] = 0;
    76.         for (int i = 1; i <= V; i++) dp[i] = -INF;
    77.         for (int i = 1; i <= N; i++)
    78.             for (int j = V; j >= v[i]; j--)
    79.                 dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    81.         cout << *max_element(dp, dp + V + 1) << endl;
    82.     }
    83. };
    85. int main() {
    86.     Solver1 s1;
    87.     Solver2 s2;
    88.     Solver3 s3;
    90.     srand(time(NULL));
    91.     int tmp = rand() % 3;
    92.     if (tmp == 0) s1.f();
    93.     else if (tmp == 1) s2.f();
    94.     else s3.f();
    95. }