1. #include <iostream>
    2. #include <vector>
    3. using namespace std;
    5. const int MAXN = 1000 + 5;
    7. int dp[MAXN][MAXN];
    9. int main() {
    10.     int N, V;
    11.     cin >> N >> V;
    12.     int v[MAXN], w[MAXN];
    13.     for (int i = 1; i <= N; i++) cin >> v[i] >> w[i];
    15.     for (int i = N; i >= 1; i--)
    16.         for (int j = 0; j <= V; j++) {
    17.             dp[i][j] = dp[i + 1][j];
    18.             if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i + 1][j - v[i]] + w[i]);
    19.         }
    21.     int val = V;
    22.     for (int i = 1; i <= N; i++) {
    23.         if (!val) {
    24.             break;
    25.         } else if (val - v[i] >= 0 && dp[i][val] == dp[i + 1][val - v[i]] + w[i]) {
    26.             cout << i << " ";
    27.             val -= v[i];
    28.         }
    29.     }
    30. }