Proof of 0/1 knapsack optimal substructure
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') &gt; 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')&gt;v(S-\{x\})$, so, adding $v(x)$ to both sides of this last equation, $v(S')+v(x)&gt;v(S-\{x\})+v(x) = v(S)$. Hence $v(S'')&gt;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$

By admissible I mean that the knapsack weighs less than the maximum weight.