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.
 A: 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.
A: 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$. 
