StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q14SE

Expert-verifiedFound in: Page 567

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**In this exercise we construct a dynamic programming algorithm for solving the problem of finding a subset S of items chosen from a set of n items where item i has a weight , which is a positive integer, so that the total weight of the items in S is a maximum but does no exceed a fixed weight limit W. Let ${\mathbf{M}}{\mathbf{(}}{\mathbf{j}}{\mathbf{,}}{\mathbf{w}}{\mathbf{)}}$ denote the maximum total weight of the items in a subset of the first j items such that this total weight does not exceed w. This problem is known as the knapsack problem.**

**a) Show that if ${{\mathit{w}}}_{{\mathbf{j}}}{\mathbf{>}}{\mathit{w}}$, then ${\mathit{M}}{\left(j,w\right)}{\mathbf{=}}{\mathit{M}}{\left(j-1,w\right)}{\mathbf{.}}$ b) Show that if ${{\mathit{w}}}_{{\mathbf{j}}}{\mathbf{\le}}{\mathit{w}}$, then $\mathbf{M}\mathbf{(}\mathbf{j}\mathbf{,}\mathbf{w}\mathbf{)}\mathbf{=}\mathbf{m}\mathbf{a}\mathbf{x}{\left(M(j-1,w),{w}_{j}+M\left(j-1,w-{w}_{j}\right)\right)}$. c) Use (a) and (b) to construct a dynamic programming algorithm for determining the maximum total weight of items so that this total weight does not exceed W****. In your algorithm store the values ${\mathbf{M}}{\mathbf{(}}{\mathbf{j}}{\mathbf{,}}{\mathbf{w}}{\mathbf{)}}$ as they are found. d) Explain how you can use the values ${\mathbf{M}}{\mathbf{(}}{\mathbf{j}}{\mathbf{,}}{\mathbf{w}}{\mathbf{)}}$computed by the algorithm in part (c) to find a subset of items with maximum total weight not exceeding W****.**

The solutions are

- $M\left(j,w\right)=M(j-1,w)$
- $M(j,w)=\hspace{0.17em}\left(M(j-1,w),{w}_{j}+M\left(j-1,w-{w}_{j}\right)\right)$
- $M(j,w)=\left\{\begin{array}{cc}M(j-1,w),& {w}_{j}>w\\ \left(M(j-1,w),{w}_{j}+M\left(j-1,w-{w}_{j}\right)\right),& {w}_{j}\le w\\ & \phantom{\rule{0ex}{0ex}}\end{array}\right.$
- $S(j,w)=\left\{\begin{array}{cc}S(j-1,w),& \text{if}M(j,w)=M(j-1,w)\\ S\left(j-1,w-{w}_{j}\right)\cup j,& \text{if}M(j,w)={w}_{j}+M\left(j-1,w-{w}_{j}\right)\\ & \phantom{\rule{0ex}{0ex}}\end{array}\right.$

Let $M(j,w)$denote the maximum total weight of the items in a subset of the first j items such that this total weight does not exceed w.

**A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms.**

Given: Set of $n$ items with item $i$ having weight ${w}_{i}$(which we assume is an integer).

$M\left(j,w\right)$ Maximum total weight of the items in a subset of the first $j$ items such that this total weight does not exceed $w$.If ${w}_{j}>w$, then this means that the weight of item $j$ exceeds $w$ and thus we cannot include item $j$(as it weights too much). The maximum total weight among the first $j$ items will then have to be the same as the maximum total weight among the first $j-1$ items (as we cannot include item $j$ in the subset corresponding to the maximum total weight).

$M\left(j,w\right)=M(j-1,w)$

If ${w}_{j}\le w,$then this means that the weight of item $j$ exceeds $w$ and thus we can include item $j$ (but we don't have to when there is a maximum total weight when not including $j$ ).

First case We include item $j$ in the maximum total weight, then the maximum total weight will be the maximum total weight of the first $j-1$items increased by the weight of item $j$ . Note: The maximum total weight of the first items cannot exceed $w-{w}_{j}$, because else the maximum total weight including item will exceed $w$ .

${w}_{j}+M\left(j-1,w-{w}_{j}\right)$

Second case We do not include item $j$ in the maximum total weight, then the maximum total weight will be the maximum total weight of the first $j-1$items (as we do not include item $j$ ).

$M(j-1,w)$

Conclusion We want to maximize the total weight, while we know that either the first or second case has the maximum total weight. Thus, to maximum the total weight, we can then take the maximum of the two cases.

$M(j,w)=\hspace{0.17em}\left(M(j-1,w),{w}_{j}+M\left(j-1,w-{w}_{j}\right)\right)$

Initially, when the set contains only 1 item, then the maximum total weight is the weight of the item (if the weight does not exceed $w$ ).

$M(1,w)=\left\{\begin{array}{cc}{w}_{1}& {w}_{1}\le w\\ 0& \text{otherwise}\\ & \phantom{\rule{0ex}{0ex}}\end{array}\right.$

When $w$ is zero, then the maximum total weight is also 0 (because the maximum total weight is nonnegative and cannot exceed $w$ ).

$M\left(j,0\right)=0$

We then use the result of part (a) and (b) to compute the maximum total weight for $j=2,3,...,n$while for each $j-$value we loop through the weights $1,2,...w$.

$M(j,w)=\left\{\begin{array}{cc}M(j-1,w),& {w}_{j}>w\\ \left(M(j-1,w),{w}_{j}+M\left(j-1,w-{w}_{j}\right)\right),& {w}_{j}\le w\\ & \phantom{\rule{0ex}{0ex}}\end{array}\right.$

You can record the subsets with maximum total weight along with the value $M(j,w).$

When $M(1,w)={w}_{1}$ , then the subset $S(1,w)$contains $\left\{1\right\}$ .

$S(1,w)=1$

When $M(j,0)=0$ , then the subset $S(j,0)$ is the empty set $\varnothing $.

$S(j,0)=0$

When $M(j,w)=M(j-1,w)$, then the subset is the same as the subset for the first $j-1$ items (as the th item is not included).

When $M(j,w)={w}_{j}+M(j-1,w-{w}_{j})$, then item $j$ is added to the subset.

$S(j,w)=\left\{\begin{array}{cc}S(j-1,w),& \text{if}M(j,w)=M(j-1,w)\\ S\left(j-1,w-{w}_{j}\right)\cup j,& \text{if}M(j,w)={w}_{j}+M\left(j-1,w-{w}_{j}\right)\\ & \phantom{\rule{0ex}{0ex}}\end{array}\right.$

94% of StudySmarter users get better grades.

Sign up for free