Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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 $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. This problem is known as the knapsack problem.
a) Show that if $w_{j} > w$ , then $M (j, w) = M (j - 1, w) .$ b) Show that if $w_{j} \leq w$ , then $M (j, w) = m a x (M (j - 1, w), w_{j} + M (j - 1, w - w_{j}))$ . 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 $M (j, w)$ as they are found. d) Explain how you can use the values $M (j, w)$ computed by the algorithm in part (c) to find a subset of items with maximum total weight not exceeding W.

The solutions are

$M (j, w) = M (j - 1, w)$
$M (j, w) = (M (j - 1, w), w_{j} + M (j - 1, w - w_{j}))$
$M (j, w) = \{\begin{matrix} M (j - 1, w), & w_{j} > w \\ (M (j - 1, w), w_{j} + M (j - 1, w - w_{j})), & w_{j} \leq w \end{matrix}$
$S (j, w) = \{\begin{matrix} S (j - 1, w), & if M (j, w) = M (j - 1, w) \\ S (j - 1, w - w_{j}) \cup j, & if M (j, w) = w_{j} + M (j - 1, w - w_{j}) \end{matrix}$

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Given data

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.

Step 2: Definition

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

Step 3: Show the following equation of part (a)

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

$M (j, w)$ 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 (j, w) = M (j - 1, w)$

Step 4: Show the following equation of part (b)

If $w_{j} \leq 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 (j - 1, w - w_{j})$

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) = (M (j - 1, w), w_{j} + M (j - 1, w - w_{j}))$

Step 5: Show the following equation of part (c)

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) = \{\begin{matrix} w_{1} & w_{1} \leq w \\ 0 & otherwise \end{matrix}$

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

$M (j, 0) = 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) = \{\begin{matrix} M (j - 1, w), & w_{j} > w \\ (M (j - 1, w), w_{j} + M (j - 1, w - w_{j})), & w_{j} \leq w \end{matrix}$

Step 6: Show the following equation of part (d)

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 ${1}$ .

$S (1, w) = 1$

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

$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) = \{\begin{matrix} S (j - 1, w), & if M (j, w) = M (j - 1, w) \\ S (j - 1, w - w_{j}) \cup j, & if M (j, w) = w_{j} + M (j - 1, w - w_{j}) \end{matrix}$

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1: Given data

Step 2: Definition

Step 3: Show the following equation of part (a)

Step 4: Show the following equation of part (b)

Step 5: Show the following equation of part (c)

Step 6: Show the following equation of part (d)

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1: Given data

Step 2: Definition

Step 3: Show the following equation of part (a)

Step 4: Show the following equation of part (b)

Step 5: Show the following equation of part (c)

Step 6: Show the following equation of part (d)

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths