# Prove that a greedy algorithm selects the maximum number of programs

This is a homework problem. Intuitively, I know it to be true, because the largest group of programs (say, $j$ programs) must be composed of the smallest $j$ programs. But how to go about formally proving this? If anyone could point me in the right direction, that would be great.

Problem Statement:

Let $P_1, P_2, ..., P_n$ be $n$ programs to be stored on a disk with capacity $D$ megabytes. Program $P_i$ requires $s_i$ megabytes of storage. We cannot store them all because $D < \sum_{i=1}^n s_i$.\

Does a greedy algorithm that selects programs in order of nondecreasing $s_i$ maximize the number of programs held on the disk? Prove or give a counterexample.

-

Without loss of generality, let us assume that $s_1 \leq s_2 \leq s_3 \leq \cdots \leq s_n$. Let the greedy algorithm choose the first $m$ program $P_1,P_2,\ldots,P_m$. The space occupied by the greedy algorithm is $$S_{\text{greedy}} = P_1 + P_2 + \cdots + P_m$$ We hence have that $$P_1 + P_2 + \cdots + P_m + P_{m+1} > D \tag{\star}$$ Let another algorithm choose $l$ programs, where $l \geq m+1$. Let these programs be $P_{a(1)},P_{a(2)}, \ldots, P_{a(l)}$, where $a(k)$ are distinct and form an increasing sequence. The space occupied by these programs is $$S_{\text{algorithm}} = P_{a(1)} + P_{a(2)} + \cdots + P_{a(l)}$$

Now note that since $a(k)$ is an increasing sequence, we have $$a(k) \geq k \implies P_{a(k)} \geq P_k\tag{\perp}$$ Hence, we get that $$S_{\text{algorithm}} \geq P_1 + P_2 + \cdots + P_l = \underbrace{P_1 + \cdots + P_m + P_{m+1}}_{>D} + \sum_{k=m+2}^l P_k \,\,\,\,\,\,\,\,\,(\because l \geq m+1)$$ Contradiction. Hence, $l \leq m$. $(\star)$ and $(\perp)$ are the crucial ingredients.

-
Should the sentence be "since $a(k)$ is an increasing sequence, we have $$a(l) \geq k \implies P_{a(l)} \geq P_k$$"? –  SSumner Apr 19 '13 at 4:19
@SSumner No. $a(k) \geq k$ is true for every $k$. –  user17762 Apr 19 '13 at 4:22
Why is that? $a(1) \geq 1$? –  SSumner Apr 19 '13 at 4:27
@SSumner $a(k)$'s are the program numbers, i.e, they are numbers from $1,2,\ldots,n$ and we have them increasing order, i.e., $a(1) < a(2) < a(3) < \cdots < a(k) <\cdots < a(l)$. From this can you conclude that $a(k) \geq k$? –  user17762 Apr 19 '13 at 4:29
@SSumner $a(1) \geq 1$. Since $a(2) > a(1)$, we get that $a(2) \geq 2$. Similarly, since $a(3)>a(2)$, we get that $(3) \geq 3$ and so on to get $a(k) \geq k$. –  user17762 Apr 19 '13 at 5:02

This algorithm does maximize the number of programs on disk. Because there are a finite number of combinations of programs to choose from we know the maximum exists. Suppose $M$ is the set of programs on the disk that maximize the number of programs on disk. If $P_i\notin M$ and $s_i \lt s_j$ for some $P_j\in M$ we can replace $P_j$ with $P_i$ and the number of programs is the same. We can continue this process until there are no more such $P_i$.

-