knapsackProblem.cpp

#include <vector>
using namespace std;

vector<int> getKnapSackIndex(vector<vector<int>> items, vector<vector<int>> dp, int capacity){
	vector<int> sol;
	int i=items.size();
	int j=capacity;
	
	while(i > 0) {
		if(dp[i][j] == dp[i-1][j]){
			i--;
		} 
		else {
			sol.push_back(i);
			j-=items[i-1][1];
			i--;
		}
		if(j == 0) break;
	}
	
	std::reverse(sol.begin(),sol.end());
	return sol;
}

vector<vector<int>> knapsackProblem(vector<vector<int>> items, int capacity) {
  // Write your code here.
  // Replace return below.
	vector<vector<int>> dp(items.size()+1, vector<int>(capacity+1, 0));
	for(int i = 1; i<items.size()+1; i++){
		for(int j = 1; j<capacity+1; j++){
			
			if(j < items[i-1][1]){
				dp[i][j] = dp[i-1][j];
			}
			else {
				dp[i][j] = dp[i-1][j-items[i-1][1]] + items[i-1][0];
			}
		}
	}
	
	vector<int> v = getKnapSackIndex(items, dp, capacity);
	
	return {{dp[items.size()][capacity]}, {v.begin(), v.end()}};
}