3
$\begingroup$

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?

Thanks in advance!

$\endgroup$
1
$\begingroup$

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(S') \leq 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$

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

$\endgroup$
  • $\begingroup$ I'm still reading the answer, but I think you meant $S' \neq S - \{x\}$ in the first line, right? $\endgroup$ – matheuscscp May 15 '16 at 19:33
  • $\begingroup$ @matheuscscp Exactly, I made an edit immediately after posting, but I guess I wasn't fast enough. Glad I could help. For maximum profit, try reproducing this proof yourself in three days time. $\endgroup$ – Lieuwe Vinkhuijzen May 15 '16 at 19:59
  • $\begingroup$ I'm doing it right now, adapted for the algorithm I'm proposing as my undergrad final project. Thank you so much! $\endgroup$ – matheuscscp May 15 '16 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.