Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We want to solve the simple knapsack problem: We're given a set of $n$ positive item weights, which are unique integers $\{w_1, \ldots , w_n\}$, and an integer $C > 0$, representing the capacity of the knapsack. The sum of the item weights is greater than C. We need to choose some set of items to put into our knapsack, using any amount of each of the available items, such that we reach the maximum capacity using the fewest items possible. Also, we are guaranteed that it is always possible to reach the maximum capacity with the given set of item weights.

Our algorithm works like so: find the heaviest item that will fit into the knapsack, and put it into the knapsack. Iterate until you can't add any more items.

We want to prove that this algorithm always produces the optimal solution.

Whether or not this algorithm works depends on the input: if we get $\{w_1 = 1, w_2 = 2, w_3 = 4\}$, and aim for $12$, then it'll choose $\{4, 4, 4\}$. Great! But if we get $\{w_1 = 2, w_2 = 6, w_3 = 8\}$, and aim for $12$, then it'll choose $\{8, 2, 2\}$. Bad! The optimal solution is $6,6$! So a counter-example exists, but I want to arrive at this disproof by contradiction.

First, some definitions: Let's define a "promising solution", $S_i$, to be a partial solution developed by the algorithm on iteration $i$, that can be extended into some optimal solution by the addition of some items of $\{w_i, \ldots , w_n\}$. That is, a partial solution is promising if it is a subset of an optimal solution.

We're going to prove that at each step of the algorithm, for any $i$ in $1,\ldots,n$, the partial solution $S_i$ is promising. Then, we'll be able to conclude that since it's promising at $S_n$, then it produces an optimal solution for the whole problem.

  • Base case: For i=0, the partial solution $S_0 = \emptyset$ is promising, because it is a trivial subset of any optimal solution.

  • Inductive hypothesis: Assume that for some fixed arbitrary $i$, where $0 \le i \le n-1$, $S_i$ is promising, i.e. there exists an optimal solution $OPT_i$ such that $S_i \subseteq OPT_i$. (Despite the subscript $i$, $OPT_i$ is a full solution. The subscript $i$ just means it's related to $S_i$.

  • Inductive Step: We want to prove that $S_{i+1}$ is promising, i.e. there exists $OPT_{i+1}$ such that $S_{i+1} \subseteq OPT_{i+1}$.

    • Case 1: Our algorithm chooses some item $w_{i+1}$ to put into the sack, and we look at $OPT_i$ and it has that item too! Fantastic. So we can construct $OPT_{i+1} = OPT_i$, and then $S_{i+1}$ is promising because $S_{i+1} \subseteq OPT_{i+1}$.

    • Case 2: Our algorithm chooses some item $w_{i+1}$ to put into the sack, but we look at $OPT_i$ and it does not have that item. Whoops! But our algorithm chose the largest item that would fit, so if $OPT_i$ isn't using that item, then it must be using at least 2 smaller items to fill up the same weight. But if it's using 2 items when it could be using 1, then it must not be optimal! But this is a contradiction, because $OPT_i$ is optimal, by the inductive hypothesis. Therefore, Case 2 cannot happen.

Therefore, by mathematical induction, our greedy algorithm produces promising partial solutions for all iterations $1,\ldots,n$, and hence produces the optimal solution to the whole problem.

But that's not true! Where did the proof go wrong?

share|improve this question
    
$S_0$ does not imply $S_1$ so your induction breaks. –  John Habert Mar 2 at 0:33
    
"it must be using at least 2 smaller items to fill up the same weight" This is false, it might be using 2 smaller items to fill up more weight –  dani_s Mar 2 at 0:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.