recursiveKnapsack.cpp

#include <iostream>
#include <iomanip>
using namespace std;
#define MAX 20

int table[MAX + 1][MAX + 1] = { 0 };
int n, wt[MAX + 1], val[MAX + 1], max_wt;

int fmax(int a, int b) {
	return a > b ? a : b;
}

int MNSack(int i, int j) {
	if (table[i][j] >= 0) return table[i][j];
	if (j < wt[i])
		return table[i][j] = MNSack(i - 1, j);
	else
		return table[i][j] = fmax(MNSack(i - 1, j), val[i] + MNSack(i - 1, j - wt[i]));
}


void items_picked(int i, int j) {
	cout << "\n Items picked : " << endl;
	while (i > 0) {
		if (table[i][j] == table[i - 1][j])   // if value does not change in table column-wise, item isn't selected
			i--;                                        // i-- goes to next item
		else                                            // if it changes, it is selected
		{
			cout << " Item " << i << endl;
			j -= wt[i];                            // removing weight from total available (j)
			i--;                                        // next item
		}
	}
}

int main() {

	srand(time(NULL));
	cout << " Enter the number of items : ";
	n = MAX;
	cout << n << endl;
	cout << " Enter the Maximum weight : ";
	max_wt = (rand() % (MAX)) + 1;
	cout << max_wt << endl;
	cout << endl;
	for (int i = 1; i <= n; i++) {
		cout << " Enter weight and value of item " << i << " : ";
		wt[i] = (rand() % (MAX)) + 1;
		val[i] = (rand() % (MAX)) + 1;
		cout << wt[i] << " " << val[i] << endl;
	}

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= max_wt; j++)
			table[i][j] = 0;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= max_wt; j++)
			table[i][j] = -1;

	cout << " Optimum value : " << MNSack(n, max_wt);

	cout << " \n Table : \n";
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= max_wt; j++)
			if (table[i][j] == -1)
				cout << setw(5) << "-";
			else
				cout << setw(5) << table[i][j];
		cout << endl;
	}

	items_picked(n, max_wt);

	return 0;
}