Skip to content

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!)