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

המבנה הרקורסיבי

נגדיר כ$m(i,j)$ את מקסימום הרווח מפיסת בד במידות $(i,j)$.‏

מימוש רקורסיבי נאיבי

הפסוודו-קוד הבא מראה מימוש פשוט לנוסחה הנ"ל:

Max-Value(i, j)
1	max-value = 0

	# Check horizontal cuts.

	# This loop means the C-language loop for(i' = 1; i' < i; ++i')
2	for i' in [1, ..., i - 1]
3		guess = Max-Value(i', j) + Max-Value(i - i', j)		
4		if guess > max-value
5			max-value = guess
		
	# Check vertical cuts.

	# This loop means the C-language loop for(j' = 1; j' < j; ++j')
6	for j' in [1, ..., j - 1]
7		guess = Max-Value(i, j') + Max-Value(i, j - j')		
8		if guess > max-value
9			max-value = guess

	# Check the worth of this shape.

19	guess = Value(i, j)
	
11	if guess > max-value
12		max-value = guess

13	return max-value

שימוש בmemoization

כרגיל, נוסיף מבנה נתונים פשוט (במקרה זה המטריצה תבנית:קוד בשורה) כדי לשמור את הערכים שכבר חישבנו:

1	M = Make-Matrix(m, n)

2	for i in [1, ..., m]
3		for j in [1, ..., n]
4			M[i][j] = Nil


Max-Value(i, j)
1	if M[i, j] != Nil
2		return M[i, j]

4	max-value = 0

	# Check horizontal cuts.

5	for i' in [1, ..., i - 1]
6		guess = Max-Value(i', j) + Max-Value(i - i', j)		
7		if guess > max-value
8			max-value = guess
		
	# Check vertical cuts.

9	for j' in [1, ..., j - 1]
10		guess = Max-Value(i, j') + Max-Value(i, j - j')		
11		if guess > max-value
12			max-value = guess

	# Check the worth of this shape.

13	guess = Value(i, j)
	
14	if guess > max-value
15		max-value = guess
		
16	M[i, j] = max-value

17	return max-value

הדפסת החלטות החיתוך

שוב כרגיל, כדי לשמור גם את סדרת הפעולות (ולא רק תוצאתן), נוסיף עוד מבנה נתונים פשוט (במקרה זה המטריצה תבנית:קוד בשורה):

1	M = Make-Matrix(m, n)
2	C = Make-Matrix(n, n)

3	for i in [1, ..., m]
4		for j in [1, ..., n]
5			M[i][j] = Nil
6			C[i][j] = Nil


Max-Value(i, j)
1	if M[i, j] != Nil
2		return M[i, j]

3	max-value = 0

	# Check horizontal cuts.

4	for i' in [1, ..., i - 1]
5		guess = Max-Value(i', j) + Max-Value(i - i', j)		
6		if guess > max-value
7			max-value = guess
8			C[i][j] = ('Horizontal', i')
		
	# Check vertical cuts.

9	for j' in [1, ..., j - 1]
10		guess = Max-Value(i, j') + Max-Value(i, j - j')		
11		if guess > max-value
12			max-value = guess
13			C[i][j] = ('Vertical', j')

	# Check the worth of this shape.

14	guess = Value(i, j)
	
15	if guess > max-value
16		max-value = guess
17		C[i][j] = ('Shape', 0)
		
18	M[i, j] = max-value

19	return max-value

המטריצה תבנית:קוד בשורה היא מטריצה של זוגות (בשפת C היינו ממשים זאת בעזרת מטריצה של מבנים):

1. האיבר הראשון בכל זוג הוא מחרוזת, המתארת איזו משלוש האפשרויות היא בחרנו.
2. האיבר השני בכל זוג הוא מספר המתאר היכן חתכנו.

הנה הקוד המדפיס את סדרת הפעולות:

Print-Cuts(i, j)
1	Print('For the best value of ' + i + ' and ' + j)

2	(type, index) = C[i][j]

3	if type == 'Horizontal'
4		Print 'Cut horizontally at ' + index
5		Print-Cuts(index, j)
6		Print-Cuts(i - index, j)
7	else if type == 'Vertical'
8		Print 'Cut vertically at ' + index
9		Print-Cuts(i, index)
10		Print-Cuts(i, j - index)
11	else
12		Print 'Use the shape itself'

ניתוח סיבוכיות

נגדיר כ$T^{\prime }(i,j)$ את סיבוכיות תבנית:קוד בשורה בהנחה שכל קריאה רקורסיבית היא $O(1)$. קל מאד לראות מהקוד ש$T^{\prime }(i,j)=\mathrm{\Theta }(i+j)$. נשים לב גם ש$\mathrm{\Theta }(i+j)=O(m+n)$, ולכן $T^{\prime }(i,j)=O(m+n)$. סיבוכיות $Max-Cuts(m,n)$ חסומה מלמעלה על ידי $\sum _{i=1}^m\sum _{j=1}^n[T^{\prime }(i,j)]=\sum _{i=1}^m\sum _{j=1}^n[O(m+n)]=O(m\cdot n\cdot (m+n))$.

גם כאשר לוקחים בחשבון את האתחול והדפסת הפרטים, הפתרון עדיין $O(m\cdot n\cdot (m+n))$.