מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/סכום תת קבוצה/תשובה

תוכל לראות הסבר לגבי המבנה הרקורסיבי של הבעיה בפרק המדבר על חשיבה רקורסיבית

נפתור את הבעיה בשני אופנים: מלמטה למעלה, ומלמעלה למטה.

פתרון מלמטה למעלה

Subset-Sum(A, t)
1	Sum = Make-Array(t)
	
2	for j in [t … 1]
3		Sum[j] = False
		
4	n = Length(A)
	
5	for i in [1, … n]
6		for j in [t … 1]
7			if j== A[i]
8				Sum[j] = True
9			if t > A[i] and Sum[t - A[i]] == True
10				Sum[j] = True
				
11	return Sum[t] == True

1-3 מייצרות מערך Sum באורך $\displaystyle t$, ומאתחלות את כל איבריו לFalse. הלולאה 5-10 עוברת על כל איברי A. לכל איבר כזה, 6-10 מעדכנת לTrue כל תא בSum שברור שניתן להגיע אליו מסכום האיברים שנבדקו עד כה. כל שנותר ב11 הוא להחזיר האם ניתן להגיע לסכום t.

שימו לב: חשוב שהלולאה ב6 תהיה בסדר יורד. אותה הלולאה בסדר עולה תניב פתרונות שגויים.

קל לראות שהסיבוכיות היא $\displaystyle \Theta (n\cdot t)$.

פתרון מלמעלה למטה

Subset-Sum(A, i, t')
1	if t == 0
2		return True
		
3	if i == 0
4		return False
		
5	if SS[i, t'] != Nil
6		return SS[i, t']
	
7	if Subset-Sum(A, i - 1, t') == True
8		SS[i, t'] = True
9		return True
		
10	if  t' ≥ A[i] and Subset-Sum(A, i - 1, t' - A[i]) == True
11		SS[i, t'] = True
12		return True
		
13	SS[i, t'] = False
14	return False

(נניח שSS היא מטריצה בעלת $\displaystyle n$ שורות ו$\displaystyle t$ עמודות, המאותחלת כולה לNil. בנייתה תארך $\displaystyle \Theta \left(n\cdot t\right)$.)

סיבוכיות הפתרון שוב פעם $\displaystyle \Theta \left(n\cdot t\right)$: אתחול המטריצה עולה $\displaystyle \Theta \left(n\cdot t\right)$. כמו כן, נגדיר כ$\displaystyle T'(i,t')$ את זמן הריצה של Subset-Sum(i, t') בהנחה שכל קריאה רקורסיבית אורכת $\displaystyle O(1)$. קל לראות ש$\displaystyle T'(i,t')=O(1)$.‏ הסיבוכיות הכוללת של הקריאות היא $\displaystyle \sum _{i=1}^{n}\sum _{t'=1}^{t}\left[T'(i,t')\right]=\sum _{i=1}^{n}\sum _{t'=1}^{t}\left[O(1)\right]=\Theta \left(n\cdot t\right)$.