/***************************************************************
* Name: Prof. Rafael Orta
* Course: Computer Science & Programming
* Class: CS04225
*****************************************************************
* Purpose: Demonstrate the use recursion for the knapsack problem
* and the Greedy algorithm.
*****************************************************************/
#include<iostream>
using namespace std;
//function prototype check recursive every subset of items
int knapsack (int w[], int p[], int n, int M);
int executions = 0;
int main ()
{
int n; //number of items
int M; //capacity of knapsack
cout << "Enter the no. of items ";
cin >> n;
int w[n]; //weight of items
int p[n]; //value of items
cout << "Enter the weight and price of all items" << endl;
for (int i = 0; i < n; i++)
{
cin >> w[i] >> p[i];
}
cout << "enter the capacity of knapsack ";
cin >> M;
cout << "The maximum value of items that can be put into knapsack is " << knapsack (w, p, n, M);
cout << "\nThe recursive function was called: " << executions << " times" << endl;
return 0;
}
//function prototype check recursive every subset of items
int knapsack (int w[], int p[], int n, int M)
{
executions++;
//cout << "\nWeight: " << w[n-1] << " Value: " << p[n-1] << " Items: " << n << " Capacity: " << M << endl;
//In every pass, we can either include nth item or not
//if the capacity of knapsack is left to NIL, no value can be attained
if (M == 0)
return 0;
//if no more items are left, no value can be attained
if (n == 0)
return 0;
//if current item, weighs more than the capacity of knapsack, it can not be included
if (w[n - 1] > M)
return knapsack (w, p, n - 1, M);
//else select the maximum value of once including the current item and once not including it
return max (knapsack (w, p, n - 1, M),
p[n - 1] + knapsack (w, p, n - 1, M - w[n - 1]));
}
/*
In general use, nil (a contraction of Latin "nihil") means "nothing" or the absence of something.
Sometimes nil is used to mean the number zero (0). In programming, nil refers to an empty set or a
list containing no entries. In some usages, nil is interchangeable with null.
*/
