Dynamic programming: knapsack, LCS and edit distance
Solve two-dimensional DP problems: the 0/1 knapsack with item reconstruction, the longest common subsequence behind diff tools, and edit distance behind spell checkers.
0/1 knapsack
best[i, w] = the best value using the first i loads with capacity w. For load i there are two choices: leave it (best[i − 1, w]) or take it if it fits (value + best[i − 1, w − weight]).
(string Name, int Weight, int Value)[] loads ={ ("Rebar", 5, 10), ("Bolts", 4, 40), ("Panels", 6, 30), ("Anchors", 3, 50)};int capacity = 10, n = loads.Length; var best = new int[n + 1, capacity + 1]; // row 0: no loads, value 0for (int i = 1; i <= n; i++){ var (_, wt, val) = loads[i - 1]; for (int w = 0; w <= capacity; w++) { best[i, w] = best[i - 1, w]; // leave load i if (wt <= w) best[i, w] = Math.Max(best[i, w], val + best[i - 1, w - wt]); // take it }}Console.WriteLine($"Best value: {best[n, capacity]}"); // Walk back: if the value changed from the row above, load i was takenvar taken = new List<string>();for (int i = n, w = capacity; i > 0; i--) if (best[i, w] != best[i - 1, w]) { taken.Add(loads[i - 1].Name); w -= loads[i - 1].Weight; }taken.Reverse();Console.WriteLine(string.Join(", ", taken));Best value: 90 Bolts, Anchors
best[w] = max(best[w], val + best[w − wt])). Looping upwards would let a load be taken again and again, which is the “unbounded” knapsack.
Longest common subsequence
diff and Git show changes.
L[i, j] = LCS length of the first i letters of A and the first j letters of B. If the last letters match, they extend the LCS of the shorter prefixes (diagonal + 1). If not, drop the last letter of one word or the other and take the better result.
Console.WriteLine(Lcs("STEEL", "STEAL"));Console.WriteLine(Lcs("ABCBDAB", "BDCABA")); static string Lcs(string a, string b){ var L = new int[a.Length + 1, b.Length + 1]; for (int i = 1; i <= a.Length; i++) for (int j = 1; j <= b.Length; j++) L[i, j] = a[i - 1] == b[j - 1] ? L[i - 1, j - 1] + 1 // match: extend the diagonal : Math.Max(L[i - 1, j], L[i, j - 1]); // drop a letter from one side var sb = new System.Text.StringBuilder(); // walk back to read the letters for (int i = a.Length, j = b.Length; i > 0 && j > 0;) { if (a[i - 1] == b[j - 1]) { sb.Insert(0, a[i - 1]); i--; j--; } else if (L[i - 1, j] >= L[i, j - 1]) i--; else j--; } return $"{L[a.Length, b.Length]} \"{sb}\"";}4 "STEL" 4 "BCBA"
Edit distance
D[i, j] for the first i letters of A and j of B. If the letters match, copy the diagonal; otherwise 1 + the cheapest of replace (diagonal), delete (above) and insert (left).
Console.WriteLine(EditDistance("KITTEN", "SITTING"));Console.WriteLine(EditDistance("STEEL", "STEAL"));Console.WriteLine(EditDistance("COLUMN", "COLUMNS"));Console.WriteLine(EditDistance("BEAM", "BEAM")); static int EditDistance(string a, string b){ var D = new int[a.Length + 1, b.Length + 1]; for (int i = 0; i <= a.Length; i++) D[i, 0] = i; // delete everything for (int j = 0; j <= b.Length; j++) D[0, j] = j; // insert everything for (int i = 1; i <= a.Length; i++) for (int j = 1; j <= b.Length; j++) D[i, j] = a[i - 1] == b[j - 1] ? D[i - 1, j - 1] // letters match: free : 1 + Math.Min(D[i - 1, j - 1], Math.Min(D[i - 1, j], D[i, j - 1])); // replace, delete, insert return D[a.Length, b.Length];}3 1 1 0
| Problem | State | Time | Used in |
|---|---|---|---|
{ 1, 5, 11, 5 } → True (11 and 1 + 5 + 5); { 1, 2, 3, 5 } → False. Use a one-dimensional knapsack-style table of booleans.
Show a hint
can[s] = some subset sums to s. For each load, loop s downwards from target to the load’s weight: can[s] |= can[s − weight].
Show the solution
Console.WriteLine(CanSplitEvenly(new[] { 1, 5, 11, 5 }));Console.WriteLine(CanSplitEvenly(new[] { 1, 2, 3, 5 })); static bool CanSplitEvenly(int[] loads){ int total = loads.Sum(); if (total % 2 != 0) return false; int target = total / 2; var can = new bool[target + 1]; can[0] = true; // the empty group foreach (int w in loads) for (int s = target; s >= w; s--) // downwards: each load used once can[s] |= can[s - w]; return can[target];}True False
Remember
0/1 knapsack: best[i, w] = max(leave item i, take it + best of the rest); walk back to find the items. Loop capacity downwards in a 1-D table to use each item once; upwards allows repeats. LCS and edit distance fill a table over two prefixes; the traceback gives the actual alignment. Two-dimensional DP is O(n · m) time; often one row of memory is enough when only the value is needed.