0
$\begingroup$

I am trying to prove correctness of Knapsack algorithm below:

Algorithm works by taking rations of values of items to weights and then sort them in decreasing order taking $O(n\log{n})$ time. So to prove that the solution is optimal, first let us setup some notations:

Setup: we have a group of items with $b_1, b_2, \cdots, b_n$ and their associated weights $w_1, \cdots, w_n$. And we are given capacity weight $W$. So we take their ratios $\frac{b_i}{w_i}$ in the algorithm below and follow the steps:

  • We keep adding highest ratio it[em $largest(\frac{b_i}{w_i}) $one at a time and then removing it from the sorted list.
  • Subtract the weight of that added ration from total weight $W-w_i$.

Algorithm below (Courtesy to Goodrich et al.): enter image description here

Proof: the prove of correctness goes as follows by contradiction, which assumes that our solution or approach that we followed above in the algorithm is basically not optimal. Steps of the proof are as follows:

  1. There is an item $i$ with higher value than a chosen item $j$, but $x_i < w_i$ and $v_i > v_j$.
  2. If we substitute $i$ with $j$ we get a better solution.
  3. How much of $i$: $min\{w_i(1-x_i), w_jx_j\}$.
  4. Thus there is no better solution than the greedy 1!

Problems 1: I don't really understand what, "there is an item $i$ with higher value than a chosen item $j$, but $x_i < w_i$ and $v_i > v_j$" means here? What I understood that there is an item $i$ with higher value $\frac{b_i}{w_i}$ than item $j$ $\frac{b_j}{w_j}$, which means $\frac{b_i}{w_i} > \frac{b_j}{w_j}$ if I am not wrong that we did not select (meaning we did not select $i$ with largest value). So what this notation $x_i < w_i$ means in $x_i < w_i ~ and ~ v_i > v_j$ above please in step (1) of the algorithm?

Problem 2: if we substitute $i$ with $j$ we get a better solution. I understand that this is because $v_i > v_j$, meaning fraction of $i$ has greater value than of $j$ and thus adding it will lead to an optimal solution. I am not sure if this is how it's interpreted please?

Problem 3: I don't really get what this whole third step means, " How much of $i$: $min\{w_i(1-x_i), w_jx_j\}$."?

Problem 4: How that conclusion was made please in the 4th step of proof, " 4. Thus there is no better solution than the greedy 1."

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.