Adjustment to Greedy Knapsack Algorithm to Guarantee Atleast 50% value of Optimal

Question

How can we change the greedy knapsack algorithm a little bit to guarantee at least 50% value of optimal?

Answer 1

Add a 3rd step to the original algorithm states: Return MAX {the Greedy Algorithms's solution, the most valuable item}.

Claim:

The new 3-steps algorithm guarantees at least 50% value of the optimal solution.

Proof:

1. Recall items have been sorted by its profit(value/weight). Assume the 2nd step of this solution returns a result includes the first k items (a₁,a₂...a_k), since items cannot be divided, a_k is the last item included, and a_k+1 is the first item excluded. Therefore, the result of this step will be at least equal to the total value of the first k items. That's RESULT1 = a_{1 +} a_{2 +} ...+ a_k.
2. Consider an alternative - a_max, where a_max is the most valuable item.  Therefore, RESULT2 = a_max >= a_k+1.
3. We choose RESULT = max{RESULT1, RESULT2}
4. Here comes the cool part. Plus the two in-equations, We have (RESULT1 + RESULT2) = a_{1 +} a_{2 +} ...+ a_k + a_k+1, which is the total value of the first k+1 items, which is also >= the fractional solution we talked about earlier (because the fractional solution takes at most the (k+1)-th item), and also the fractional solution will be at least equal to the optimal solution of this problem because the fractional solution consume all knapsack's capacity and choose items by its profit in decending order.
5. So we have: RESULT >= RESULT1, and RESULT >= RESULT2.  That is, we have, 2 * RESULT  >=  RESULT1 + RESULT2 = Value(1,k+1) >= the fractional solution >= the optimal solution. That's 2 * RESULT >= Optimal solution.  That is, RESULT >= 0.5 * Optimal Solution.

I wrote an article contains more details about this problem: Knapsack Problem