0/1 knapsack and longest common subsequence
Goal and connection
Use the preceding DP state/transition/base/order/reconstruction method. Two-dimensional states prevent information loss when progress depends on both an item/prefix boundary and another constraint. This lesson supplies two standard families without assuming a greedy shortcut.
1. 0/1 knapsack state
Items 1,...,n have positive integer weights w_i and nonnegative values v_i; capacity W is a nonnegative integer. Each item may be taken once or not at all. K[i,c] is maximum value using only the first i items with total weight at most c. K[0,c]=0 and K[i,0]=0. For c<w_i, K[i,c]=K[i−1,c]. Otherwise:
K[i,c]=max(K[i−1,c], v_i+K[i−1,c−w_i]).
An optimum either excludes item i or includes it once. The remaining problem in both cases uses only items 1,...,i−1, which prevents reuse. Fill i increasing, c=0,...,W. The answer is K[n,W]. This is an at-most-capacity state, so unused capacity is allowed; exact-fill variants need different unreachable-state initialization.
Example W=5, items (weight,value)=(2,3),(3,4),(4,5). Rows c=0..5 are K[0]=[0,0,0,0,0,0]; K[1]=[0,0,3,3,3,3]; K[2]=[0,0,3,4,4,7]; K[3]=[0,0,3,4,5,7]. Answer 7 takes items 1 and 2. Reconstruct from (n,W): if K[i,c]=K[i−1,c], skipping i is valid; otherwise take i and subtract w_i. In either case decrement i; stop at i=0. Full-table traceback takes O(n) time, including its at-most-n selected items. Ties can choose either optimal branch consistently.
2. Space compression has an order requirement
Full table time O(nW), space O(nW). For value only, one array dp[c] uses O(W) space and suffices if each item processes c downward from W to w_i: dp[c]=max(dp[c],v_i+dp[c−w_i]). The smaller index has not yet been updated for the current item, so it still means the previous row. Ascending c can reuse the same item and instead implements an unbounded pattern. For one item (2,3), W=4, ascending updates dp[2]=3 then dp[4]=6, an illegal double use. Downward gives 3. Do not promise direct reconstruction from a value-only compressed array without additional decision information or recomputation. O(nW) is pseudo-polynomial in binary-encoded W.
3. Longest common subsequence
A subsequence preserves order but may skip positions; it need not be contiguous. For strings X of length m and Y of length n, L[i,j] is the LCS length of prefixes X[1..i],Y[1..j]. Base row and column are zero. If X[i]=Y[j], L[i,j]=1+L[i−1,j−1]. Otherwise L[i,j]=max(L[i−1,j],L[i,j−1]). Fill rows or columns so both shorter prefixes are ready.
If final symbols match, there exists an optimum ending with that common symbol; append it to an optimum of the shorter prefixes. If they differ, a common subsequence cannot use both as a matched final pair, so at least one final position is skipped, giving the two alternatives. This is about positions, not deleting every occurrence of a character.
Worked example X=ABC, Y=AC. With columns empty,A,C, rows are empty:[0,0,0]; A:[0,1,1]; AB:[0,1,1]; ABC:[0,1,2]. Answer 2 reconstructs AC, which skips B. At matching endpoints, record the symbol and move diagonally; otherwise move to a neighbor with equal optimal value. Stop when either prefix length is zero and reverse the recorded symbols at the end. Traceback takes O(m+n) time, including its output. Ties can yield different LCS strings with the same length.
4. Costs and distinctions
LCS time O(mn), full reconstruction table space O(mn); length alone can use rolling rows in O(min(m,n)) space. Standard simple rolling rows alone do not retain the full traceback. LCS is not longest common substring: substring requires contiguity and a different transition. Count states and work per state separately in both families, and distinguish numerical capacity from string length when discussing input size.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. 0/1 knapsack include transition uses which row?
A. i B. i−1 C. i+1 D. Always row 0
Answer: B
A: Can reuse the same item.
B: Only earlier items remain eligible.
C: Future items are outside the state.
D: Would exclude all useful previous items.
P02. W=5, items (2,3),(3,4),(4,5): optimum value?
A. 5 B. 6 C. 7 D. 12
Answer: C
A: One item of weight 4 is worse.
B: No feasible subset has value 6; value 7 is attained by items 1 and 2.
C: First two weigh 5 and value 7.
D: All items exceed capacity.
P03. One-array 0/1 update should traverse capacity:
A. Ascending B. Descending C. Random order always valid D. Only zero
Answer: B
A: Can reuse current item.
B: Preserves previous-row source values.
C: Dependencies can be overwritten.
D: Positive-weight items need positive capacity.
P04. LCS length of ABC and AC?
A. 0 B. 1 C. 2 D. 3
Answer: C
A: A and C are common in order.
B: AC has two symbols.
C: AC is a common subsequence.
D: The shorter string has only two symbols.
P05. When final LCS-prefix symbols differ, use:
A. 1+L[i−1,j−1] B. max(L[i−1,j],L[i,j−1]) C. L[i−1,j−1]−1 D. Always zero
Answer: B
A: Cannot match unequal symbols.
B: Skip one of the two final positions.
C: Lengths cannot be decremented this way.
D: Earlier prefixes may share symbols.
P06. Which distinction is correct?
A. Subsequence must be contiguous B. Substring may skip arbitrary positions C. Subsequence preserves order but may skip positions D. LCS always uses all symbols
Answer: C
A: Contiguity is a substring requirement.
B: Skipping defines subsequences, not substrings.
C: This is the subsequence definition.
D: Some symbols may be excluded.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in