C++ Algorithms: 0-1 Knapsack and LCS Implementation
Classified in Computers
Written on in 
English with a size of 2.52 KB
Knapsack Problem: Recursive Approach
The following code demonstrates a naive recursive implementation of the 0-1 Knapsack problem in C++.
/* A Naive recursive implementation of 0-1 Knapsack problem */
#include <bits/stdc++.h>
using namespace std;
// A utility function that returns the maximum of two integers
int max(int a, int b) { return (a > b) ? a : b; }
// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
// Base Case
if (n == 0 || W == 0)
return 0;
// If weight of the nth item is more than Knapsack capacity W,
// then this item cannot be included in the optimal solution
if (wt[n - 1] > W)
return knapSack(W, wt, val, n