Knapsack Problem

• Time : O(cap * n)
• Space : O(cap)

#include <vector>
using namespace std;

vector<vector<int>> knapsackProblem(vector<vector<int>> items, int cap) {
    int ma = 0, pos = 0, n = items.size();
    vector<pair<int, int>> dp(cap + 1, {-1, -1});
    dp[0] = {0,-1};
    for(int j = 0; j < n; j++) {
        int c = items[j][0], w = items[j][1];
        for(int i = cap; i >= w; i--) {
            if(i - w == -1) continue;
            if(dp[i].first < dp[i-w].first + c) {
                dp[i] = {dp[i-w].first + c, j};
                if(ma < dp[i].first) {
                    ma = dp[i].first;
                    pos = i;
                }
            }
        }
    }
    vector<int> res;
    while(pos) {
        res.push_back(dp[pos].second);
        pos -= items[res.back()][1];
    }
    return {
            {ma},   // total value
            res, // item indices
    };
}