Homework 2: Consider the biggest sum problem

Homework 2

1. Consider the biggest sum problem. The input to this problem is a list of
integers and a target integer t. The output is a subset of the list whose sum
is as close to t as possible without going over. Prove that the algorithm
below does not find the correct elements for every possible input.
Input: values: an array of integers
Input: n: the length of values
Input: t: the target integer
Output: a subset of values whose sum is as close to t as possible without
going over
1 Algorithm: GreedySum
2 Sort values in decreasing order (i.e., max-first)
3 sum = 0
4 select = {}
5 for i = 1 to n do
6 if values[i] + sum < t then
7 Add values[i] to select
8 sum = sum + values[i]
9 end
10 end
11 return select
1