# Proof of 0/1 knapsack optimal substructure

I'm trying to understand why exactly the 0/1 knapsack problem actually has the optimal substructure property.

Let $E$ be the set of items to consider and $v$ and $w$ the value and weight functions defined over $E$.

Now, suppose that, among all solutions weighing at most $W$, $S \subseteq E$ is the best solution. How can I prove that $S - \{x\}$ is the best solution weighing at most $W - w(x)$, considering the set of possible items as $E - \{x\}$? I tried to suppose that $S' \subseteq E - \{x\}$ is a better solution (that is, $v(S') > v(S - \{x\})$ and $w(S') \leq W - w(x)$), but I get stuck when I try to find a contradiction.

Any help?

Suppose that some $$S'\subseteq E-\{x\}$$ is a better admissible solution than $$S-\{x\}$$. Then $$S'\not= S$$, the value is more, $$v(S') > v(S-\{x\})$$, and $$x\not \in S'$$, and $$w(S')\leq W-w(x)$$, as you indicated. Now add $$x$$ to $$S'$$ to obtain $$S''=S'\cup \{x\}$$. What will be the value and weight of this new subset? And how does it compare to the value and weight of $$S$$? Let's write it out:
$$w(S'') = w(S')+w(x) \leq (W-w(x))+w(x) = W$$ so $$S''$$ weighs less than $$W$$, so $$S''$$ is an admissible solution, so it makes sense to compare their values.
$$v(S'') = v(S') + v(x)$$. By assumption, $$v(S')>v(S-\{x\})$$, so, adding $$v(x)$$ to both sides of this last equation, $$v(S')+v(x)>v(S-\{x\})+v(x) = v(S)$$. Hence $$v(S'')>v(S)$$. But this is a contradiction, because $$S''$$ is supposedly a better admissible solution while you had presumed that $$S$$ was the best admissible solution. $$\square$$
• I'm still reading the answer, but I think you meant $S' \neq S - \{x\}$ in the first line, right? – matheuscscp May 15 '16 at 19:33