рюкзак с восстановлением ответа

vector<vector<pair<int>>> p(n + 1, vector<int>(M + 1))
for (int i = 1; i <= n; i++) {
    for (int s = 0; s <= M; s++) {
        if (w[i - 1] < s) {
            dp[i][s] = dp[i - 1][s];
            continue;
        }
        if (dp[i - 1][s] > dp[i - 1][s - w[i - 1]] + cost[i - 1]) {
              p[i][s] = {i - 1, s};
              dp[i][s] = dp[i - 1][s];
        } else {
              p[i][s] = {i - 1, s - w[i - 1]};
              dp[i][s] = dp[i - 1][s - w[i - 1]] + cost[i - 1];
        }
    }
}
vector<int> answ;
pair<int, int> cur = {n, m};
while (cur.fi != 0) {
    if (cur.se != p[cur.fi][cur.se].se) {
        answ.push_back(cur.fi);
    }
    cur = p[cur.fi][cur.se];
}
cout << dp[n][m] << '\n';
for (auto e : answ) cout << e << ' ';