1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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