Create a gist now

Instantly share code, notes, and snippets.

Embed
Select items from knapsack 1-0 problem - www.spoj.com/problems/KNAPSACK/
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment