# Correctness proof of greedy algorithm for 0-1 knapsack problem

We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an optimal solution.

Given the two orders I imagined that we could just choose the first k elements from either sequence and use them to fill knapsack until it was full. This would be similar to choosing the items with the greatest ratio of value to weight. But I don't think that is an optimal solution.

So what I need help with is whether or not this solution is optimal. And how would I prove the correctness of a greedy algorithm.

• I suggest you try a few examples to see if this works. If all examples seem to work, try formulating a proof along the lines you saw in class. If the proof doesn't work, try designing a counterexample according to the step which seems to fail. – Yuval Filmus Mar 26 '14 at 3:39

Hint: Let $x$ be the item of smallest weight (and so of highest value). Take any solution which doesn't contain $x$. If there is room for $x$, add it to the solution. Otherwise, remove some element and add $x$ (why is that possible? does it necessarily improve the solution?). Conclude that the optimal solution always contains $x$. Apply this reasoning recursively to come up with a greedy algorithm.

• Ok thank you. I see after doing a few examples how I can use this. – Ryan Smith Mar 26 '14 at 3:45
• You can skip the recursion/induction and just use an exchange argument: assume the optimal solution is strictly better than the greedy solution. If the optimal solution is not the same as the greedy, then there is some pair of items i,j with i<j in the ordering, where the optimal solution contains j but excludes i. Trade j for i, and show that this is always feasible and always at least as good. That contradicts the assumption that the optimal solution was better than the greedy one. – DMGregory Mar 27 '14 at 13:25

A simple solution would be like this:

1. Generate solution using GREEDY technique.
2. Calculate permutation of all possible answers, and see for the max profit satisfying weight constraint
3. Now, you can check that your solution generated by GREEDY technique, and the permutation which yields max profit satisfying constraint is the same, then you can say that your algorithm is correct.

Let O be the optimal solution.

O = {o1, o2, o3 ..., oj}


Let G be our greedy solution.

G = {g1, g2, g3, ..., gk}


K = Initial Weight = Empty Knapsack

K = k - 0              //Initially


If g1 is in O then we are done.

But if g1 does not exist in O, then there might be another optimum solution.

O' = O - {g1}          Equation : 1
K' = K - {g1}          Equation : 2   //Which means w1(least weight)


If O' does not make an optimal solution then, our claim is wrong that g1 does not exist in O.

Therefore,

O' = K'   // Since the optimum solution should have next weight possible
O' = K - {g1}          From Equation : 2
O' = O - {g1}          From Equation : 1
O - {g1} = K - {g1}    Equating


So, O = K

which proves that, The optimal solution after removing g1 from O' is still O.

Q.E.D

• Please check my solution and tell me if there are more suggestions. This is a similar proof as mentioned above. Just trying to use cs.stackexchange for good. – technazi Oct 22 '16 at 22:01
• I don't understand what you're doing, here. You say that, if $g_1\notin O$, there is another optimal solution $O'=O\setminus\{g_1\}$. But, if $g_1\notin O$, then $O'$ isn't "another optimal solution" -- it's exactly the same solution as $O$. – David Richerby Oct 22 '16 at 22:54
• Yes, It could be wrong or could be ambiguous. What i am trying to do is, State O as the optimum solution ; Check if g1 belongs to O ; If it doesn't then find another optimal solution from the existing optimal solution after removing g1. ; If it can not find the solution then my assumption is wrong. ; – technazi Oct 22 '16 at 22:57
• I still don't understand. You talk about trying to remove $g_1$ from a solution that doesn't contain it. That doesn't change the solution. – David Richerby Oct 22 '16 at 23:00
• please feel free to edit if this is potentially correct. – technazi Oct 22 '16 at 23:01