Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
@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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.