Analysis of Algorithms : An Active Learning Approach

9.1 GREEDY APPROXIMATION ALGORITHMS 237

pass of this algorithm considers additional cases. The first pass begins with the
empty set and adds items in decreasing order until the limit is reached or all of
the items have been tried. The second pass begins with all of the possible sets of
one item from the list and adds more items from there. The third pass begins
with all of the possible sets of two items. The more time that is available, the
more passes that the algorithm can do. If there are 10 items in the input and 11
passes can be done, the optimal solution will be found. You should see that, for
10 items, on the first pass there is 1 empty set, on the second pass there are 10
sets of one element, and on the third pass there are 45 sets of two elements.
The sixth pass will be the worst with 252 sets of five elements. So, even though
this process might sound simple, it can still take a significant amount of time.
The algorithm for one pass of this process is
SubsetSum(sizes, N, limit, pass, result, sum)
sizes the list of item sizes
N the number of items in the list
limit the maximum sum for the subset
pass used to set the number of items in the starting set
result the items in the best subset found
sum the sum of the items in result

sum = 0
for each subset T of {1,..,n} with pass items do
tempSum = 0
for i = 1 to N do
if i ∈ T then
tempSum = tempSum + sizes[i]
end if
end for
if tempSum ≤ limit then
for j = 1 to N do
if j ∉ T and tempSum + sizes[j] ≤ limit then
tempSum = tempSum + sizes[j]
T = T ∪ {j}
end if
end for
end if
if sum < tempSum then
sum = tempSum
result = T
end if
end for