Proof by contradiction for greedy algorithms

Question

I'm having some difficulty understanding/being convinced the technique used to prove a greedy algorithm is optimal for the fractional knapsack problem. A proof by contradiction is used. I've never been great at proofs, and maybe this will help me get on the track to becoming more comfortable with them.

Consider section 3.2, Analysis. https://www2.cs.duke.edu/courses/fall17/compsci330/lecture6note.pdf The algorithm is very intuitive - choose the highest value/weight and only the last item in the knapsack may need be fractional. I don't have any issues with that. Formally proving that this algorithm is the best thing out there I what I have an issue with.

(note proof is available in more detail: https://www2.cs.duke.edu/courses/fall17/compsci330/lecture6.pdf)

The professor shows that our algorithm chooses items p_1...p_n in various amounts. ALG = (p_1, p_2, ... , p_n). So we choose p_1 much of item 1, p_2 much of item2... all the way to p_n. Only the last item in the knapsack could be fractional. All good.

Now we assume that there exists a better algorithm, OPT. We say OPT makes the same choices as ALG up to a certain point OPT(q_1, q_2,...q_n). At some point, q_i, OPT makes a different choice that ALG. Why in the notes does the professor say q_i cannot be p_1. Surely OPT could take a different choice immediately. Anyway, that aside, I agree that OPT, like ALG will be putting as much of the items it can into the knapsack upto i. After i, OPT starts doing something else. The professor doens't talk about this, but maybe OPT changes the ordering of the items it puts into the knapsack - that wouldn't be a big deal as long as it chose all the same items and put the same amount of the very last item ALG put in the knapsack last.

However changing the order of items chosen wouldn't make OPT better, just the same. Right? (professor doesn't talk about this, at least not explicitly). For OPT to be better there must be some item, i it chooses less than ALG did of. And similarly some item j we take more of than ALG did, to keep the capacity the same. Another aside: haven't we made the implicit assumption that we must use all of the capacity, W, to be optimal. Is this self evident or something? Intuitively I can see why, but formally I cannot.

Anyway we remove a little amount from qj and give it to qi, hence those equations involving epsilon. i.e. if we remove e units of weight of j then we can add (e * wj / wi) units of value. Fine.

Now why on earth is this called OPT'. Isn't this still OPT? I'm confused here. Why did we bring OPT' in there? Why do we need yet another modified version of ALG. I thought OPT (not OPT') is where we modified qi and qj by changing how much of each we picked.

Thanks all!

Answer 1

Just think like this. Without loss of generality, assume

$\begin{equation*} \dfrac{v_1}{w_1} > \dfrac{v_2}{w_2} > \dotsb > \dfrac{v_n}{w_n} \end{equation*}$

(item types with same $v_i/w_i$ can be merged, it doesn't matter in the end).

Let ALGs choices be $p_1, p_2, \dotsc, p_n$, OPTs choices be $q_1, q_2, \dotsc, q_n$.

Assume ALG doesn't give an optimal solution, so $\mathbf{p} \ne \mathbf{q}$. As they are different, there is $i$ such that $p_k = q_k$ for $1 \le k \le i$ and $p_i \ne q_i$. By the way ALG works, it adds as much of $i$ as it possibly can, so $p_i > q_i$. What OPT looses by this against ALG on $i$ is $(p_i - q_i) \cdot v_i / w_i$, and it more than makes up the loss by adding $(p_i - q_i)$ weight of items that are all worth less per weight than $i$. That is impossible.

Answer 2

Basically, the argument is an "exchange argument" and proceeds as the following:

Say that ALG produces a knapsack $P$ with choices $p_1, p_2, \dots , p_n$ which amounts to weight $W$ (the knapsack can only hold this total weight).

Suppose that there is an optimal knapsack such that it maximizes the value per weight added, and this knapsack is optimal and $P$ is not, call this optimal knapsack $OPT$.

So $P$ and $OPT$ have the same weight up until some point, and the same overall value for the total weight in each of the knapsacks (the value/weight is the same for both $P$ and $OPT$ up to some point). Let $W_i < W$ be the point prior to where knapsacks $P$ and $OPT$ weight diverges, that is after $W_i$, knapsacks $P$ and $OPT$ now have different weights.

We claim that at this point, $W_i$, we can replace the corresponding weight in $OPT$ that leads to divergence, with some amount of weight (could be fractional) from $P$, while strictly not decreasing the value/weight in knapsack $OPT$. Since the greedy algorithm picks the best weight to put in the knapsack $P$ based on highest value/weight (as stated above, the items are sorted in decreasing value/weight order) then clearly the exchange in weight from $P$ to $OPT$ does not decrease the optimality of value/weight in the knapsack $OPT$. We can keep doing this exchange until $OPT$ is literally the same knapsack as $P$, recall $P$ is the knapsack that ALG (greedy algorithm) produces.

Therefore, we have proved by contradiction there cannot be a strictly more optimal knapsack than the knapsack produced by ALG, so $P$ is optimal and ALG produces the optimal knapsack. $\blacksquare$