Select items from knapsack 1-0 problem - www.spoj.com/problems/KNAPSACK/

knapsack-select.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v, c;
vector< vector<int> > DP;

void pick(int i, int w)
{
	if (i <= 0 || w <= 0) return;

	int k = DP[i][w];
	if (k != DP[i - 1][w]) {
		cout << i << " "; // select!
		pick(i - 1, w - c[i]); // capacity decreases
	} else {
		// move on to next item; capacity no change
		pick(i - 1, w);
	}
}

int main()
{
	int S, N; cin >> S >> N;

	// sloted for easy array access; values won't be used.
	c.push_back(-1);
	v.push_back(-1);

	int st, vt;
	for (int i = 0; i < N; i++) {
		cin >> st >> vt;
		c.push_back(st);
		v.push_back(vt);
	}

	DP.resize(N + 1, vector<int>(S + 1, 0));

	for (int i = 1; i <= N; i++) { // i is scope of items in consideration
		for (int w = 1; w <= S; w++) { // j is max size of bag
			if (c[i] > w) {
				DP[i][w] = DP[i - 1][w];
			} else {
				DP[i][w] = max(DP[i - 1][w], v[i] + DP[i - 1][w - c[i]]);
			}
		}
	}

	cout << "Selected items: ";
	pick(N, S);
}