0/1 knapsack

#include<bits/stdc++.h>
#define int long long
using namespace std;

int v[1010], w[1010], dp[1010];
bool bac[1010][1010];

signed main(){
    int n, W;
    cin >> n >> W;
    for(int i=0;i<n;i++) cin >> w[i] >> v[i];

    // dynamic programming
    for(int i=0;i<n;i++){
        for(int j=W;j>=0;j--){
            if(j-w[i] >= 0){
                if(dp[j-w[i]]+v[i] > dp[j])
                    dp[j] = dp[j-w[i]]+v[i], bac[i][j] = true;
            }
        }
    }
    cout << dp[W] << endl;

    // backtracking
    int i = n-1, j = W;
    while(i >= 0 && j >= 0){
        if(bac[i][j] == true){
            cout << i << ' ';
            j-=w[i], i--;
        }
        else i--;
    }
    cout << endl;
}