We start this section with designing a dynamic programming algorithm for the knapsack problem:

**The Knapsack Problem and Memory Functions**

We start this section with
designing a dynamic programming algorithm for the knapsack problem: given ** n** items of known weights

To design a dynamic
programming algorithm, we need to derive a recurrence relation that expresses a
solution to an instance of the knapsack problem in terms of solutions to its
smaller subinstances. Let us consider an instance defined by the first ** i** items, 1 ≤

**
**Among the subsets that do not include the ** i**th item, the value of an optimal subset is, by
definition,

**
**Among the subsets that do include the ** i**th item (hence,

Thus, the value of an optimal
solution among all feasible subsets of the first ** i** items is the maximum of these two values. Of
course, if the

Our goal is to find ** F (n, W ),** the maximal value of a
subset of the

Figure 8.4 illustrates the
values involved in equations (8.6) and (8.7). For ** i, j > **0

The dynamic programming
table, filled by applying formulas (8.6) and (8.7), is shown in Figure 8.5.

Thus, the maximal value is ** F (**4

The time efficiency and space
efficiency of this algorithm are both in ** (nW ).** The time needed to find the
composition of an optimal solution is in

**Memory
Functions**

As we discussed at the
beginning of this chapter and illustrated in subsequent sections, dynamic
programming deals with problems whose solutions satisfy a recurrence relation
with overlapping subproblems. The direct top-down approach to finding a
solution to such a recurrence leads to an algorithm that solves common
subproblems more than once and hence is very inefficient (typically,
exponential

or worse). The classic
dynamic programming approach, on the other hand, works bottom up: it fills a
table with solutions to *all* smaller
subproblems, but each of them is solved only once. An unsatisfying aspect of
this approach is that solutions to some of these smaller subproblems are often
not necessary for getting a solution to the problem given. Since this drawback
is not present in the top-down approach, it is natural to try to combine the
strengths of the top-down and bottom-up approaches. The goal is to get a method
that solves only subproblems that are necessary and does so only once. Such a
method exists; it is based on using *memory*** functions**.

This method solves a given
problem in the top-down manner but, in addition, maintains a table of the kind
that would have been used by a bottom-up dynamic programming algorithm.
Initially, all the table’s entries are initialized with a spe-cial “null”
symbol to indicate that they have not yet been calculated. Thereafter, whenever
a new value needs to be calculated, the method checks the correspond-ing entry
in the table first: if this entry is not “null,” it is simply retrieved from
the table; otherwise, it is computed by the recursive call whose result is then
recorded in the table.

The following algorithm
implements this idea for the knapsack problem. After initializing the table,
the recursive function needs to be called with ** i** =

**ALGORITHM** *MFKnapsack**(i, j )*

//Implements the memory function
method for the knapsack problem //Input: A nonnegative integer ** i** indicating the number of the first

items being considered and a nonnegative integer ** j** indicating

the knapsack capacity

//Output: The value of an
optimal feasible subset of the first ** i** items //Note: Uses as global variables input
arrays

**if ***F*** **[*i, j*** **]** ***<*** **0

**if ***j
<*** ***Weights*[** i**]

*value *←* MFKnapsack**(i** *−* *1*, j )*

**else**

*value *←* *max*(**MFKnapsack**(i** *−* *1*, j ),*

*Values*[** i**]

** F **[

**EXAMPLE
2 **Let us apply the memory function method to the instance consid-ered
in Example 1. The table in Figure 8.6 gives the results. Only 11 out of 20
nontrivial values (i.e., not those in row 0 or in column 0) have been computed

Just one nontrivial entry, ** V (**1

In general, we cannot expect
more than a constant-factor gain in using the memory function method for the
knapsack problem, because its time efficiency class is the same as that of the
bottom-up algorithm (why?). A more significant improvement can be expected for
dynamic programming algorithms in which a computation of one value takes more
than constant time. You should also keep in mind that a memory function
algorithm may be less space-efficient than a space-efficient version of a
bottom-up algorithm.

**a. **Apply the bottom-up dynamic programming algorithm to the following** **instance of the knapsack problem:

**
**How many different optimal subsets does the instance of part (a)
have?

In general, how can we use
the table generated by the dynamic program-ming algorithm to tell whether there
is more than one optimal subset for the knapsack problem’s instance?

**
****a. **Write pseudocode of the
bottom-up dynamic programming algorithm for**
**the knapsack problem.

**
**Write pseudocode of the algorithm that finds the composition of an
optimal subset from the table generated by the bottom-up dynamic programming
algorithm for the knapsack problem.

**
**For the bottom-up dynamic programming algorithm for the knapsack
prob-lem, prove that

**
**its time efficiency is * (nW ).*

**
**its space efficiency is ** (nW )**.

**
**the time needed to find the composition of an optimal subset from a
filled dynamic programming table is *O(n).*

**
****a. **True or false: A sequence of
values in a row of the dynamic programming**
**table for the knapsack problem is always nondecreasing?

**
**True or false: A sequence of values in a column of the dynamic
program-ming table for the knapsack problem is always nondecreasing?

**
**Design a dynamic programming algorithm for the version of the
knapsack problem in which there are unlimited quantities of copies for each of
the ** n** item kinds given. Indicate
the time efficiency of the algorithm.

**
**Apply the memory function method to the instance of the knapsack
problem given in Problem 1. Indicate the entries of the dynamic programming
table that are (i) never computed by the memory function method, (ii) retrieved
without a recomputation.

**
**Prove that the efficiency class of the memory function algorithm
for the knap-sack problem is the same as that of the bottom-up algorithm (see
Problem 3).

**
**Explain why the memory function approach is unattractive for the
problem of computing a binomial coefficient by the formula ** C(n, k)** =

** C(n **−

**
**Write a research report on one of the following well-known
applications of dynamic programming:

**
**finding the longest common subsequence in two sequences

**
**optimal string editing

**
**minimal triangulation of a polygon

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Dynamic Programming : The Knapsack Problem and Memory Functions |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.