Explain the proof of allocation problem
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 &lt; \cdots &lt; 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$.