Share
Explore BrainMass

SubSet Sum using Greedy & Dynamic Algorithms

1. SubsetSum (greedy algorithms)
A SubsetSum is defined as follows: given positive integers a1 . . . an (not necessarily distinct), and a positive integer t, find a subset S of (1 . . . n) such that ∑iε s ai = t, if it exists.
a) Suppose each ai is at least twice as large as the sum of all smaller numbers aj . Give a greedy algorithm to solve SubsetSum under this assumption.
b) Prove correctness of your greedy algorithm by stating and proving the loop invariant.

2) SubsetSum (dynamic programming) Now suppose that the ai values are arbitrary. Design a dynamic programming algorithm to solve the SubsetSum problem. The running time of your algorithm should be polynomial in both n and t.
a) Give the definition of the array A you will use to solve this problem and state how you find out if there is such a set S from that array.
b) Give the recurrence to compute the elements of the array A, including initialization.
c) State how you would recover the actual set S given A .
d) Analyze the running time of your algorithm (including the step reconstructing S), in terms of n and t. hide problem.

Solution Preview

Please see the attachment.

Problem #1 (Greedy Algorithm)
Suppose A is the array of positive integers with length n and it is sorted by the decreasing order. That is, A[0] >= A[1] >= A[2] >= ... >= A[n-1], t is a positive integer. We want to find a subset of A, such that the sum of the subset is equal to t. Suppose the subset is S.
(a) Here is the greedy algorithm.
SubSetSum(A, t, S)
BEGIN
1. Set S = {};
2. For i = 0 To n-1 Do
2.1 If t >= A[i] Then Do
2.1.1 S = S + A[i];
2.1.2 t = t - A[i];
2.2 End If
3. End For
4. If t==0 Then Return S
Else print "There is no solution. "
END
(b) Now I prove the correctness of the above algorithm.
The loop 2 is going from the biggest element to the smallest element of the array A. If t is greater than or equal to some A[i], then this A[i] must be in the subset S. ...

Solution Summary

Subset Sums using greedy and dynamic algorithms are examined in the solution.

$2.19