0/1 knapsack और longest common subsequence
लक्ष्य और संबंध
पिछले DP पाठ का state/transition/base/order/reconstruction method लगाएँ। Item/prefix boundary और दूसरी constraint दोनों जरूरी हों तो two-dimensional state सूचना बचाता है। यहाँ दो standard families हैं; greedy shortcut नहीं माना गया।
1. 0/1 knapsack state
Items 1,...,n के positive integer weights w_i, nonnegative values v_i और nonnegative integer capacity W हैं। हर item अधिकतम एक बार। K[i,c]=पहले i items से total weight अधिकतम c रखते हुए maximum value। K[0,c]=0, K[i,0]=0। c<w_i पर K[i,c]=K[i−1,c], अन्यथा:
K[i,c]=max(K[i−1,c], v_i+K[i−1,c−w_i])।
Optimum item i छोड़ता या एक बार लेता है। दोनों में remainder केवल पहले i−1 items का है, इसलिए reuse नहीं। i बढ़ाते हुए और c=0,...,W भरें। Answer K[n,W]। यह at-most capacity है; unused capacity मान्य। Exact-fill variant में unreachable initialization अलग चाहिए।
उदाहरण W=5, (weight,value)=(2,3),(3,4),(4,5)। c=0..5 पर rows: 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 items 1,2 लेता है। Reconstruction (n,W) से: K[i,c]=K[i−1,c] हो तो i छोड़ना valid; अन्यथा i लेकर c से w_i घटाएँ। दोनों में i घटाएँ; i=0 पर रुकें। Full-table traceback O(n) time लेता है, अधिकतम n selected items सहित। Tie पर कोई optimal branch consistent चुनें।
2. Space compression में order जरूरी
Full table time O(nW), space O(nW)। केवल value के लिए O(W) space का one-array dp[c] लें; हर item पर c को W से w_i तक नीचे चलाएँ: dp[c]=max(dp[c],v_i+dp[c−w_i])। छोटा index current item से update नहीं हुआ, अतः previous row है। Ascending c item reuse कर सकता है। एक item (2,3), W=4 पर ascending dp[2]=3, फिर dp[4]=6 देता है: illegal double use। Downward result 3। Compressed value array से बिना extra decisions/recomputation सीधे reconstruction का वादा न करें। Binary W के संदर्भ में O(nW) pseudo-polynomial है।
3. Longest common subsequence
Subsequence order बचाता है, positions skip कर सकता है; contiguous होना जरूरी नहीं। X length m, Y length n में L[i,j]=prefixes X[1..i],Y[1..j] की LCS length। Base row/column zero। X[i]=Y[j] हो तो 1+L[i−1,j−1], अन्यथा max(L[i−1,j],L[i,j−1])। Rows/columns ऐसे भरें कि shorter prefixes तैयार हों।
Final symbols match हों तो कोई optimum इस common symbol से समाप्त होता है; shorter prefixes के optimum में उसे जोड़ें। अलग हों तो दोनों final positions एक matched pair नहीं बन सकतीं; कम-से-कम एक छोड़ना होगा, इसलिए दो alternatives। यहाँ positions की बात है, character की सभी occurrences हटाने की नहीं।
उदाहरण X=ABC,Y=AC। Columns empty,A,C पर rows: empty:[0,0,0]; A:[0,1,1]; AB:[0,1,1]; ABC:[0,1,2]। Answer 2, reconstruction AC; B skip है। Matching endpoints पर symbol record करके diagonal जाएँ; अन्यथा equal optimal value वाले neighbor पर जाएँ। किसी भी prefix length के zero होने पर रुकें और recorded symbols reverse करें। Traceback output सहित O(m+n) time लेता है। Ties अलग LCS strings दे सकते हैं, length समान रहेगी।
4. लागत और अंतर
LCS time O(mn), full reconstruction table space O(mn)। केवल length rolling rows से O(min(m,n)) space में मिलती है। साधारण rolling rows पूरी traceback नहीं रखतीं। LCS longest common substring नहीं: substring contiguous है और transition अलग है। दोनों families में states और per-state work अलग गिनें; input size बताते समय numeric capacity और string length अलग समझें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. 0/1 knapsack include transition किस row से?
A. i B. i−1 C. i+1 D. Always row 0
उत्तर: B
A: Same item reuse हो सकता है।
B: केवल पहले items eligible हैं।
C: Future items state के बाहर हैं।
D: सभी previous items बाहर हो जाएँगे।
P02. W=5, items (2,3),(3,4),(4,5): optimum value?
A. 5 B. 6 C. 7 D. 12
उत्तर: C
A: Weight 4 वाला अकेला कम है।
B: किसी feasible subset का value 6 नहीं; items 1 और 2 से value 7 मिलता है।
C: पहले दो weight 5,value 7।
D: सभी items capacity पार करते हैं।
P03. One-array 0/1 update में capacity क्रम:
A. बढ़ता B. घटता C. कोई random क्रम सही D. केवल zero
उत्तर: B
A: Current item reuse हो सकता है।
B: Previous-row source बचता है।
C: Dependencies overwrite होंगी।
D: Positive weights को positive capacity चाहिए।
P04. ABC और AC की LCS length?
A. 0 B. 1 C. 2 D. 3
उत्तर: C
A: A,C सही क्रम में common हैं।
B: AC में दो symbols।
C: AC common subsequence है।
D: छोटी string में केवल दो symbols।
P05. LCS-prefix के अंतिम symbols अलग हों तो:
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
उत्तर: B
A: असमान symbols match नहीं।
B: दो final positions में एक skip करें।
C: ऐसे length घटाना गलत।
D: पहले prefixes common हो सकते हैं।
P06. कौन-सा अंतर सही है?
A. Subsequence contiguous जरूरी B. Substring positions skip कर सकता है C. Subsequence order बचाकर positions skip कर सकता है D. LCS सभी symbols लेता है
उत्तर: C
A: Contiguity substring में जरूरी।
B: Skipping subsequence की बात है।
C: यही subsequence की परिभाषा।
D: कुछ symbols छूट सकते हैं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Algorithms syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन