35.5 The subset-sum problem

35.5-1

Prove equation \(\text{(35.23)}\). Then show that after executing line 5 of \(\text{EXACT-SUBSET-SUM}\), \(L_i\) is a sorted list containing every element of \(P_i\) whose value is not more than \(t\).

(Omit!)

35.5-2

Using induction on \(i\), prove inequality \(\text{(35.26)}\).

(Omit!)

35.5-3

Prove inequality \(\text{(35.29)}\).

(Omit!)

35.5-4

How would you modify the approximation scheme presented in this section to find a good approximation to the smallest value not less than \(t\) that is a sum of some subset of the given input list?

(Omit!)

35.5-5

Modify the \(\text{APPROX-SUBSET-SUM}\) procedure to also return the subset of \(S\) that sums to the value \(z^\*\).

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用