Knapsack and longest common subsequence

Introduction

Many DP problems need a table with two indexes. These two appear in nearly every algorithms exam.

Once a table has two indexes, it can describe two things at once: how much of the input has been used and how much room is left, or how far along each of two strings you are. These two classics teach the pattern.

How it works

The 0/1 knapsack

#include <stdio.h>

int main(void) {
    int w[] = {1, 3, 4};      // weights
    int v[] = {15, 20, 30};   // values
    int n = 3, W = 4;
    int dp[4][5];             // dp[i][c]: best value from the first i items with capacity c
    for (int c = 0; c <= W; c++) dp[0][c] = 0;
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];   // leave item i-1
            if (w[i - 1] <= c && v[i - 1] + dp[i - 1][c - w[i - 1]] > dp[i][c])
                dp[i][c] = v[i - 1] + dp[i - 1][c - w[i - 1]];   // take it
        }
    }
    printf("best value: %d\n", dp[n][W]);
    return 0;
}

A bag holds weight W. Each item has a weight and a value, and can be taken whole or left (0 or 1, no fractions). What is the largest total value that fits?

Let dp[i][c] be the best value using only the first i items with capacity c. For item i - 1 there are two choices:

• leave it: dp[i-1][c];
• take it, if it fits: its value plus the best for the rest, v[i-1] + dp[i-1][c - w[i-1]].

dp[i][c] is the larger of the two. Row 0 (no items) is all 0. Watch the table fill row by row; the answer is the bottom-right cell. It is O(n × W).

Greedy by value per kilogram fails here, though it is correct for the fractional knapsack, where you may take part of an item.

Syntax

for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++)
        if (i == 0 || j == 0) L[i][j] = 0;
        else if (a[i - 1] == b[j - 1]) L[i][j] = L[i - 1][j - 1] + 1;
        else L[i][j] = /* the larger of L[i - 1][j] and L[i][j - 1] */;

Example

#include <stdio.h>
#include <string.h>

int main(void) {
    char a[] = "ABCB", b[] = "BDCAB";
    int n = strlen(a), m = strlen(b);
    int L[5][6];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) L[i][j] = 0;
            else if (a[i - 1] == b[j - 1]) L[i][j] = L[i - 1][j - 1] + 1;
            else L[i][j] = L[i - 1][j] > L[i][j - 1] ? L[i - 1][j] : L[i][j - 1];
        }
    }
    printf("LCS length: %d\n", L[n][m]);
    return 0;
}

A subsequence keeps some characters of a string in order, not necessarily side by side: "BCB" is a subsequence of "ABCB". The LCS of two strings is the longest subsequence of both; it measures how similar they are (diff and DNA comparison use it).

Let L[i][j] be the LCS length of the first i characters of a and the first j of b:

• if a[i-1] == b[j-1], that character extends the LCS: L[i-1][j-1] + 1;
• otherwise, drop the last character of one string: the larger of L[i-1][j] and L[i][j-1].

Row 0 and column 0 are 0 (an empty string has nothing in common). It is O(n × m). Walking back through the table from the corner recovers the subsequence itself.

Line by line

1. a and b are the two strings, and n and m are their lengths.
2. L has one extra row and column, for the empty prefixes.
3. The two loops visit each cell, with smaller indexes first, so every value it needs is already there.
4. If either prefix is empty, there is nothing in common, so the cell is 0.
5. If the last characters match, they extend the answer for the two shorter prefixes.
6. Otherwise one of the two last characters is not used, so the cell takes the better of dropping either one.
7. L[n][m] covers both whole strings, and for these two it is 3.

Expected result

LCS length: 3

In the real world

The diff tool that shows the changes between two files is based on finding a longest common subsequence. Comparing DNA and protein sequences uses closely related tables, and budget-limited selection problems are often knapsacks.

Common mistakes

• Using a[i] instead of a[i - 1]: row i means the first i characters.
• Sizing the table n by m instead of n + 1 by m + 1.
• Treating a subsequence as a run of neighbouring characters, which is a substring.

Best practices

• Fill the first few cells by hand before coding.
• Keep the off-by-one rule in a comment beside the table.
• Keep only two rows if memory matters and only the final value is needed.

Summary

Two-index DP tables describe states such as items used and capacity left, or positions in two strings. The knapsack and the longest common subsequence are filled cell by cell, and each runs in time proportional to the table's size.

Mark lesson complete