# Explain the proof of allocation problem

The problem:

There are $$N$$ houses for sale. The $$i$$-th house costs $$A_i$$ dollars to buy. You have a budget of $$B$$ dollars to spend.

What is the maximum number of houses you can buy?

There is an intuitive way to solve this problem in a greedy way: we must at first sort the house costs and then buy houses until we are out of money and it works.

and the proof is:

Let's prove the correctness of this greedy algorithm. Let the solution produced by the greedy algorithm be $$A = \{a_1, a_2, \ldots, a_k\}$$ and an optimal solution be $$O = \{o_1, o_2, \ldots, o_m\}$$.

If $$O$$ and $$A$$ are the same, we are done with the proof. Let's assume that there is at least one element $$o_j$$ in $$O$$ that is not present in $$A$$. Because we always take the smallest element from the original set, we know that any element that is not in $$A$$ is greater than or equal to any $$a_i$$ in $$A$$. We could replace $$o_j$$ with the absent element in $$A$$ without worsening the solution, because there will always be element in $$A$$ that is not in $$O$$. We then increased number of elements in common between $$A$$ and $$O$$, hence we can repeat this operation only finite number of times. We could repeat this process until all the elements in $$O$$ are elements in $$A$$. Therefore, $$A$$ is as good as any optimal solution.

I don't understand the proof and I have couple of questions:

1. What does it mean to replace $$o_j$$ with an absent element in $$A$$?
2. Why do we need to do it?

Could you explain this proof in a simpler way with examples?

You can see this problem here.

I don't like this proof so much. Here is a different one.

We can assume without loss of generality that $$A_1 \leq \cdots \leq A_N$$. Consider an optimal solution $$\{i_1,\ldots,i_\ell\}$$, where $$i_1 < \cdots < i_\ell$$. In particular, $$A_{i_1} + \cdots + A_{i_\ell} \leq B.$$ Intuitively, it is clear that $$A_1 + \cdots + A_\ell \leq B$$ (we will prove this formally in a moment), and so the greedy algorithm will also choose at least $$\ell$$ houses.

Now let us prove that $$A_1 + \cdots + A_\ell \leq A_{i_1} + \cdots + A_{i_\ell}$$.

I claim that $$i_j \geq j$$. Indeed, $$i_j \geq 1 + i_{j-1} \geq 2 + i_{j-2} \geq \cdots \geq j-1 + i_1 \geq j.$$ This implies that $$A_{i_j} \geq A_j$$, and so $$A_{i_1} + \cdots + A_{i_\ell} \geq A_1 + \cdots + A_\ell$$.