C++ Algorithms: 0-1 Knapsack and LCS Implementation

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 - 1);

    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else
        return max(
            val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
            knapSack(W, wt, val, n - 1));
}

// Driver code
int main()
{
    int profit[] = { 60, 100, 120 };
    int weight[] = { 10, 20, 30 };
    int W = 50;
    int n = sizeof(profit) / sizeof(profit[0]);
    cout << knapSack(W, weight, profit, n);
    return 0;
}

Longest Common Subsequence (LCS) via Dynamic Programming

This implementation solves the Longest Common Subsequence problem using a bottom-up Dynamic Programming approach.

// Dynamic Programming C++ implementation of LCS problem
#include <bits/stdc++.h>
using namespace std;

// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(string X, string Y, int m, int n)
{
    // Initializing a matrix of size (m+1)*(n+1)
    int L[m + 1][n + 1];

    // Following steps build L[m+1][n+1] in bottom-up fashion.
    // Note that L[i][j] contains the length of LCS of X[0..i-1] and Y[0..j-1]
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i - 1] == Y[j - 1])
                L[i][j] = L[i - 1][j - 1] + 1;
            else
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
        }
    }

    // L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1]
    return L[m][n];
}

// Driver code
int main()
{
    string S1 = "AGGTAB";
    string S2 = "GXTXAYB";
    int m = S1.size();
    int n = S2.size();

    // Function call
    cout << "Length of LCS is " << lcs(S1, S2, m, n);

    return 0;
}