Preface :
In Chapter 6, we introduced the Fibonacci sequence. A simple recursive definition describes the sequence. The first two terms are 0 and 1. All subsequent terms are the sum of the two previous values :
Fibonacci sequence : 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Recursive definition :
The method fib() uses a straightforward translation of the definition for its implementation.
The execution of the method is far from straightforward. In Section 6.3, we show that the number of method calls requested to evaluate fib(n) increase exponentially. This means that the recursive computation of fib(n) is an exponential algorithm and is so inefficient as to be impractical for even small values of n. The problem stems from all of the redundant recursive calls. For instance, the hierarchy tree in below figure illustrates the method calls required to compute fib(5)=5. The redundancy is evident when you see that the execution makes multiple calls to fib(0) ... fib(3) including five calls to fib(1).
The format for fib() has the structure of a divide-and-conquer algorithm. It lacks, however, the efficiency ordinarily associated with this technique because it fails to partition the problem into independent subproblems. Recall the design of the merge sort and quicksort algorithms that partition a list into separate (nonoverlapping) sublists. In general, when a divide-and-conquer strategy results in nonindependent subproblems, a straightforward recursive implementation often produces very poor running time because the overlap can require a prohibitive large number of redundant calculations and method calls. In this section, we develop a new technique, called dynamic programming, which can often address the problem. This technique defines an array to store intermediate results and then directly accesses values in the array rather than recomputing results.
We begin by developing a dynamic programming solution to the Fibonacci sequence problem. This introduces you to the key concepts. Many important applications involve polynomial of the form (1+x)^n. These mathematical expressions are the sum of terms consisting of binomial coefficients and powers ofx. Computing binomial coefficients is an excellent example of dynamic programming and allows us to discover both a top-down and bottom-up implementation of the technique. We conclude the section by looking at the famous knapsack problem from the field of operations research.
Top-Down Dynamic Programming :
A slight change in the algorithm for fib() allows us to reduce redundancy and produce a method with running time O(n). The approach includes, as an argument, an array that stores the return values from intermediate method calls. The recursive step first checks the array to see whether the results has already been computed. If so, it directly accesses the value without requiring redundant calculations. If not, the recursive step executes, then adds, the result to the array for later access. The top-down strategy stores values as they are computed in the recursive descent to a stopping condition. Top-down dynamic programming is also referred to as memorization.
Let us see how dynamic programming would affect the calculation of fib(5). In below figure, the unshaded nodes (blue background) with numbers below the box represents values that are stored in the array. The actual numbers indicates the order they are added to the array. The circled nodes have values that are already in the array because they involve calculations that were previously obtained. These values can be extracted from the array and thus save redundant calculations represented by the shaded (gray background) nodes.
The method fibDyn() is the top-down dynamic programming version for the fib() algorithm. The method fibDyn() includes an integer array argument with at lease n+1 elements, whose initial value are -1. The array stores intermediate Fibonacci numbers in the index range 0 to n. The recursive step identifies a nonnegative value in the array as a previously computed result :
- Running Time of fibDyn()
Below figure shows that n+1 method calls reach the bottom of the tree. On the way back up, fibDyn(1), fibDyn(2), ... fibDyn(n-2) return without performing any more recursive calls. The number of method calls to compute fibDyn(n) is n+1+(n-2) = 2n-1, so this algorithm for the computation of the Fibonacci numbers is linear :
Combinations With Dynamic Programming :
In Section 29.1, we developed the recursive method comm(), which returns the number of different combinations of n items taken k at a time. Like the recursive method fib(), evaluation of comm() involves redundant calculations. For instance, computing comm(50,6)=158,90,700 requires 3,813,767 method calls :
A top-down dynamic programming implementation of comm() stores intermediate results in the matrix (2-dimensional array) commMat, which has n+1 rows and k+1 columns, where commMat[i][j] is the solution for C(i,j). Initially, all of the values in the matrix are set to -1. Each recursive call to commDyn(n,k) first checks whether the value commMat[n][k] is nonzero. If so, it uses the matrix element as its return value :
Computing C(50,6) by using commDyn() requires only 441 method calls, a little better than the almost four million calls required by comm().
Bottom-Up Dynamic Programming :
Top-down dynamic programming is a design strategy for a recursive progress. A method implements the design by supplying a container that stores intermediate results that are derived from chains of method calls. This allow a method call to return without performing additional recursive calls. An alternative strategy, called bottom-up dynamic programming, replaces a recursive algorithm by one using a storage container and iteration. Rather than storing results as they occur in a recursive chain, bottom-up dynamic programming builds the storage container in order, starting at the lowest level. An iterative process uses previously computed values at each step to compute the next value.
Let us apply the bottom-up strategy in a new algorithm for the function C(n,k). The key is creation of a matrix that contains values C(i,j), where 0<=i<=n and 0<=j<=k. This involves computing a series of sequences :
The foruma C(n,k) = C(n-1,k) + C(n-1,k-1) indicates that we can compute intermediate values for entries in row i by using results from row i-1. Below table displays the matrix for n=6, k=6. When n=k, the table of the entries is often called Pascal's Triangle :
In the table, note that the first entry (C(i,0)) and last entry (C(i,i)) in each row i is 1. The intermediate entries C(i, j) for 1<=j<=i-1 are the sum of entries from previous row. We apply this fact to the building of a matrix that is at the core of the dynamic bottom-up design of an algorithm for function C(n,k).
The implementation of the method commDynB() that computes C(n,k) begins with the allocation of an n+1 square matrix commMat. The algorithm builds the matrix row by row starting at row 0 until it finds the value C(n,k) in row n, column k of the matrix. Note that once we have computed Pascal triangle through row k, column k, it is only necessary to compute rows k+1, k+2, ..., n through column k. Note that commMat[i][j]=1 when j==0 or j==i.
Knapsack Problem :
Operations research is a branch of mathematics that solves, among other things, optimization problems. One such example is the knapsack problem, which has a dynamic programming solutions. We are given a knapsack to hold a set of items that have specified sizes and values. The knapsack has a limited capacity, measured in volume. The problem is to find a subset of objects that will fit into the Knapsack and provide the maximum value. The problem is a prototype for many important applications. For example, it will help transport companies what want to load cargo on a truck, freight car, or ship in such a way that the cargo returns a maximum profit or a contestant who has won a shopping spree and wants to load the cart with items that represent the maximum value.
There are several versions of the knapsack problem. One version allows us to split items into fractional parts to fill up all of the space in the knapsack. For instance, a camper could cut a slab of bacon into small pieces or take only part of the bag of rice if necessary. The 0/1 version of the knapsack problem is more interesting. In this case, we are given a choice of rejecting (0) or accepting (1) an item from the collection. We explore this version.
A simple but impractical solution to the knapsack problem involves an exhaustive evaluation of every possible subset of items. Since the power set has 2^n items, the algorithm has exponential running time O(2^n). There is a dynamic programming solution that applies the principle of optimality to each item in the collection. The principle of optimality states that no matter what the first decision, the remaining decisions must be optimal with respect to any state in the algorithm that results from the first decision.
Assume we want to fill the knapsack from among a list of n items. Using bottom-up dynamic programming, we compute the values for an integer matrix maxValuMat. The row and column dimensions for the maximum are n+1 and capacity+1 respectively. The entry maxValueMat[i][cap] is the maximum value of a subset of items chosen from {item1, item2, ..., itemi}, where the total size of the elements in the subset is <= cap. Assume each item is a record with a value field and a size field. The mathematical definition of maxValueMat[i][cap] is :
where aj=1 if itemj is in the subset and aj=0 if itemj is not in the subset. After we build the matrix, matValueMat[n][capacity] is the solution to the problem.
An example will give you a clear understanding of the knapsack problem. Suppose we can select from five items to fill a knapsack that has capacity 12. In the algorithm, we build the 6 by 13 matrix maxValueMat row by row starting with row 1. For demonstration purposes, we will build three rows, which are sufficient to develop the key features of the algorithm.
Row 1 in the matrix looks at the set {item1}, which is a subset of all of the available items, and includes the element having size 2 and value 1. The task is to assign values to maxValueMat[1][cap], where 0<=cap<=capacity. This is easy. Only when cap >= 2 do we have enough space for item1. Placing it in the knapsack produces value 1. The first row of the matrix becomes :
Row2 in the matrix looks at the set{item1, item2}, where item2 has size 3 and value 4. Again, cap<2 is too small to hold nay item. With cap=2, there is room for only item1 with value 1. We begin to understand the algorithm when cap=3. Because item2.size=3<=cap, we cap place item2 in the knapsack. The effect is to create a value of 4 and leave no additional space in the knapsack (cap-item2.size=0). The new value 4 is an improvement over value 1 from maxValueMat[1][3]. A similar analysis applies to cap=4, except that placing item2 in the knapsack leaves 1 unit of unused space. For cap >=5, the knapsack has room for both items, with a total value of 5 :
For entries in row3, we look at values created by filling the knapsack with any subset of the first three items. Row2 contains the maximum value for each capacity when only the first two items are used. We need to determine whether adding the third item with size 4 and value 3 will improve the situation. When cap=4, there is sufficient space to use the item. The effect is to produce a value 3 and leave no additional space for any other item (cap-item3.size=0). From row2, we already have a value 4 by using only the first two items (maxValueMat[2][4]=4). Adding item3 doesn't improve the maximum value for the capacity, and so we retain the existing value :
maxValueMat[3][4] = maxValueMat[2][4] = 4
With cap=6, adding item3 contributes value 3 and leaves 2 units of space, sufficient to add item1. The total :
item3.value + maxValueMat[2][2]=4
is not an improvement on the existing maximum value of 5 (maxValueMat[2][6]), which we derived in row 2 by using only the first two items, and so we again retain the value from row2 :
maxValueMat[3][6] = maxValueMat[2][6]=5
When cap=7, adding item3 leaves 3 units of additional space. Using the maximum value for capacity 3(maxValueMat[2][3]=4) from row2, we have a new value 7, which is greater than the value 5, derived from using only first two items :
After completing all of the entries in row3, we have :
You have now seen all of the elements of the algorithm. In general, for row i, computing maxValueMat[i][cap] involves determining whether itemi should be part of the subset of items from set {item1, item2, ... itemi} that produces the maximum value for the specified capacity. First, test whether the new item fits in the space :
Adding itemi provides value but reduces the space available to store items from the list {item1, ..., itemi} If we use itemi, the remaining capacity is (cap-itemi.size), and the maximum value for that capacity is the matrix entry maxValueMat[i-1][cap-itemi.size]. The sum of this value and itemi.value is the best we can do for this capacity by adding itemi. On the other hand, the entry maxValueMat[i-1][cap] is the maximum value from using only the elements {item1, ..., itemi-1}. A test compares the effect of adding itemi with the value that doesn't use itemi. The matrix entry is the larger vale :
To follow up, we discuss the knapsack class that includes the private method buildMaxValueMat(), which builds the matrix by using the dynamic programming algorithm.
The Knapsack Class :
The class Item describes the items in the knapsack. Two integer variables define the size and value of an object. To simplify access, we declare the members public. A constructor creates an instance of the class using two arguments for the size and value.
The Knapsack class includes an Item array called itemList and the integer matrix (2-dimensional array) maxValueMat as instance variables, along with integer variables for the capacity and the number of items. The constructor takes a list of Item objects and a capacity as arguments and initializes the corresponding instance variables. The constructor also allocates space for the knapsack matrix. The private method buildMaxValueMat() implements the dynamic programming version of the knapsack algorithm. For output, the method displayKnapsack() displays the maximum value and the list of the items that fit into the knapsack to produce the value. The display also notes the amount of unused space :
- Building the Knapsack Matrix
We build the [row][column] entries in maxValueMat one element at a time. To simplify the calculations, all of the entries in row 0 have value 0. The outer loop uses the control variable i to scan the items in the row range 1... numItems. A inner loop uses the control variable cap to compute the column values in the range 0 ... capacity. For each entry maxValueMat[i][cap], we use the value from the previous row as its initial value.
The effect is to assume that itemList[i] will not be added to the knapsack. We override this assumption only after successfully completing a series of tests. The first test checks whether itemList[i] fits in the knapsack (cap-itemList[i].size>=0). A second test determines whether adding itemList[i] and sacrificing the space it occupies would produce a greater value. If so, the algorithm assigns the new value to the matrix entry :
- Identifying the Items
The matrix maxValueMat not only determines the maximum value for the specified capacity, it also provides information that will allow us to determine the items that fill the knapsack. The maximum value is maxValueMat[numItems][capacity], which is an entry in the last row of the matrix. Starting with this entry, we can work back through the matrix to discover the items in the knapsack. To understand the algorithm, recall how we built the matrix. In row i,maxValueMat[i][cap] is not equal to maxValueMax[i-1][cap] only if adding itemList[i] increases the value. This becomes the criterion to determine whether itemList[i] is in the knapsack.
Let us return to our example and look at maxValueMat for the capacity 12. The solution to the problem is maxValueMat[5][12]=14.
Because maxValueMat[4][12]=13 (!=maxValueMat[5][12]), itemList[5] with size 6 and value 8 is in the knapsack. There are 6 units of unused space (cap-itemList[5].size) remaining, which can be filled from the sublist itemList[1]... itemList[4]. Working backwords, maxValueMat[4][6] indicates that the sublist produces value 6. Now maxValueMat[3][6]=5 (!=maxValueMat[4][6]), so the test criterion indicates that itemList[4] with size 5 and value 6 is in the knapsack. Only 1 unit of additional space remains. Because the value maxValueMat[i][1] are identically 0 for rows 3,2, and 1, we conclude that none of the corresponding items is in the knapsack. This fact is obvious; no item would fit into 1 unit of space. We conclude that the knapsack holds itemList[5] and itemList[4] and has 1 unit of unused space.
The method displayKnapsack() implements this algorithm. A loop scans the list of items in descending order and identifies an item in the knapsack when its presence adds value. The listing of the items in the knapsack includes their size and value.
- Evaluating the Knapsack Problem Solution
The running time of our bottom-up dynamic programming solution to the knapsack problem is O(nC), where n is the number of items and C is the capacity. This follows directly from the fact that the algorithm builds a matrix of size (n+1) x (C+1) that has O(nC) elements. The amount of computation depends critically on C. For instance, if C=n the algorithm is O(n^2), but if C=2^n, the algorithm has running time O(n2^n)
Supplement :
* Gossip@Caterpillar : 常見演算法 - 背包問題
In Chapter 6, we introduced the Fibonacci sequence. A simple recursive definition describes the sequence. The first two terms are 0 and 1. All subsequent terms are the sum of the two previous values :
Fibonacci sequence : 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Recursive definition :
The method fib() uses a straightforward translation of the definition for its implementation.
The execution of the method is far from straightforward. In Section 6.3, we show that the number of method calls requested to evaluate fib(n) increase exponentially. This means that the recursive computation of fib(n) is an exponential algorithm and is so inefficient as to be impractical for even small values of n. The problem stems from all of the redundant recursive calls. For instance, the hierarchy tree in below figure illustrates the method calls required to compute fib(5)=5. The redundancy is evident when you see that the execution makes multiple calls to fib(0) ... fib(3) including five calls to fib(1).
The format for fib() has the structure of a divide-and-conquer algorithm. It lacks, however, the efficiency ordinarily associated with this technique because it fails to partition the problem into independent subproblems. Recall the design of the merge sort and quicksort algorithms that partition a list into separate (nonoverlapping) sublists. In general, when a divide-and-conquer strategy results in nonindependent subproblems, a straightforward recursive implementation often produces very poor running time because the overlap can require a prohibitive large number of redundant calculations and method calls. In this section, we develop a new technique, called dynamic programming, which can often address the problem. This technique defines an array to store intermediate results and then directly accesses values in the array rather than recomputing results.
We begin by developing a dynamic programming solution to the Fibonacci sequence problem. This introduces you to the key concepts. Many important applications involve polynomial of the form (1+x)^n. These mathematical expressions are the sum of terms consisting of binomial coefficients and powers ofx. Computing binomial coefficients is an excellent example of dynamic programming and allows us to discover both a top-down and bottom-up implementation of the technique. We conclude the section by looking at the famous knapsack problem from the field of operations research.
Top-Down Dynamic Programming :
A slight change in the algorithm for fib() allows us to reduce redundancy and produce a method with running time O(n). The approach includes, as an argument, an array that stores the return values from intermediate method calls. The recursive step first checks the array to see whether the results has already been computed. If so, it directly accesses the value without requiring redundant calculations. If not, the recursive step executes, then adds, the result to the array for later access. The top-down strategy stores values as they are computed in the recursive descent to a stopping condition. Top-down dynamic programming is also referred to as memorization.
Let us see how dynamic programming would affect the calculation of fib(5). In below figure, the unshaded nodes (blue background) with numbers below the box represents values that are stored in the array. The actual numbers indicates the order they are added to the array. The circled nodes have values that are already in the array because they involve calculations that were previously obtained. These values can be extracted from the array and thus save redundant calculations represented by the shaded (gray background) nodes.
The method fibDyn() is the top-down dynamic programming version for the fib() algorithm. The method fibDyn() includes an integer array argument with at lease n+1 elements, whose initial value are -1. The array stores intermediate Fibonacci numbers in the index range 0 to n. The recursive step identifies a nonnegative value in the array as a previously computed result :
- Running Time of fibDyn()
Below figure shows that n+1 method calls reach the bottom of the tree. On the way back up, fibDyn(1), fibDyn(2), ... fibDyn(n-2) return without performing any more recursive calls. The number of method calls to compute fibDyn(n) is n+1+(n-2) = 2n-1, so this algorithm for the computation of the Fibonacci numbers is linear :
Combinations With Dynamic Programming :
In Section 29.1, we developed the recursive method comm(), which returns the number of different combinations of n items taken k at a time. Like the recursive method fib(), evaluation of comm() involves redundant calculations. For instance, computing comm(50,6)=158,90,700 requires 3,813,767 method calls :
A top-down dynamic programming implementation of comm() stores intermediate results in the matrix (2-dimensional array) commMat, which has n+1 rows and k+1 columns, where commMat[i][j] is the solution for C(i,j). Initially, all of the values in the matrix are set to -1. Each recursive call to commDyn(n,k) first checks whether the value commMat[n][k] is nonzero. If so, it uses the matrix element as its return value :
Computing C(50,6) by using commDyn() requires only 441 method calls, a little better than the almost four million calls required by comm().
Bottom-Up Dynamic Programming :
Top-down dynamic programming is a design strategy for a recursive progress. A method implements the design by supplying a container that stores intermediate results that are derived from chains of method calls. This allow a method call to return without performing additional recursive calls. An alternative strategy, called bottom-up dynamic programming, replaces a recursive algorithm by one using a storage container and iteration. Rather than storing results as they occur in a recursive chain, bottom-up dynamic programming builds the storage container in order, starting at the lowest level. An iterative process uses previously computed values at each step to compute the next value.
Let us apply the bottom-up strategy in a new algorithm for the function C(n,k). The key is creation of a matrix that contains values C(i,j), where 0<=i<=n and 0<=j<=k. This involves computing a series of sequences :
The foruma C(n,k) = C(n-1,k) + C(n-1,k-1) indicates that we can compute intermediate values for entries in row i by using results from row i-1. Below table displays the matrix for n=6, k=6. When n=k, the table of the entries is often called Pascal's Triangle :
In the table, note that the first entry (C(i,0)) and last entry (C(i,i)) in each row i is 1. The intermediate entries C(i, j) for 1<=j<=i-1 are the sum of entries from previous row. We apply this fact to the building of a matrix that is at the core of the dynamic bottom-up design of an algorithm for function C(n,k).
The implementation of the method commDynB() that computes C(n,k) begins with the allocation of an n+1 square matrix commMat. The algorithm builds the matrix row by row starting at row 0 until it finds the value C(n,k) in row n, column k of the matrix. Note that once we have computed Pascal triangle through row k, column k, it is only necessary to compute rows k+1, k+2, ..., n through column k. Note that commMat[i][j]=1 when j==0 or j==i.
Knapsack Problem :
Operations research is a branch of mathematics that solves, among other things, optimization problems. One such example is the knapsack problem, which has a dynamic programming solutions. We are given a knapsack to hold a set of items that have specified sizes and values. The knapsack has a limited capacity, measured in volume. The problem is to find a subset of objects that will fit into the Knapsack and provide the maximum value. The problem is a prototype for many important applications. For example, it will help transport companies what want to load cargo on a truck, freight car, or ship in such a way that the cargo returns a maximum profit or a contestant who has won a shopping spree and wants to load the cart with items that represent the maximum value.
There are several versions of the knapsack problem. One version allows us to split items into fractional parts to fill up all of the space in the knapsack. For instance, a camper could cut a slab of bacon into small pieces or take only part of the bag of rice if necessary. The 0/1 version of the knapsack problem is more interesting. In this case, we are given a choice of rejecting (0) or accepting (1) an item from the collection. We explore this version.
A simple but impractical solution to the knapsack problem involves an exhaustive evaluation of every possible subset of items. Since the power set has 2^n items, the algorithm has exponential running time O(2^n). There is a dynamic programming solution that applies the principle of optimality to each item in the collection. The principle of optimality states that no matter what the first decision, the remaining decisions must be optimal with respect to any state in the algorithm that results from the first decision.
Assume we want to fill the knapsack from among a list of n items. Using bottom-up dynamic programming, we compute the values for an integer matrix maxValuMat. The row and column dimensions for the maximum are n+1 and capacity+1 respectively. The entry maxValueMat[i][cap] is the maximum value of a subset of items chosen from {item1, item2, ..., itemi}, where the total size of the elements in the subset is <= cap. Assume each item is a record with a value field and a size field. The mathematical definition of maxValueMat[i][cap] is :
where aj=1 if itemj is in the subset and aj=0 if itemj is not in the subset. After we build the matrix, matValueMat[n][capacity] is the solution to the problem.
An example will give you a clear understanding of the knapsack problem. Suppose we can select from five items to fill a knapsack that has capacity 12. In the algorithm, we build the 6 by 13 matrix maxValueMat row by row starting with row 1. For demonstration purposes, we will build three rows, which are sufficient to develop the key features of the algorithm.
Row 1 in the matrix looks at the set {item1}, which is a subset of all of the available items, and includes the element having size 2 and value 1. The task is to assign values to maxValueMat[1][cap], where 0<=cap<=capacity. This is easy. Only when cap >= 2 do we have enough space for item1. Placing it in the knapsack produces value 1. The first row of the matrix becomes :
Row2 in the matrix looks at the set{item1, item2}, where item2 has size 3 and value 4. Again, cap<2 is too small to hold nay item. With cap=2, there is room for only item1 with value 1. We begin to understand the algorithm when cap=3. Because item2.size=3<=cap, we cap place item2 in the knapsack. The effect is to create a value of 4 and leave no additional space in the knapsack (cap-item2.size=0). The new value 4 is an improvement over value 1 from maxValueMat[1][3]. A similar analysis applies to cap=4, except that placing item2 in the knapsack leaves 1 unit of unused space. For cap >=5, the knapsack has room for both items, with a total value of 5 :
For entries in row3, we look at values created by filling the knapsack with any subset of the first three items. Row2 contains the maximum value for each capacity when only the first two items are used. We need to determine whether adding the third item with size 4 and value 3 will improve the situation. When cap=4, there is sufficient space to use the item. The effect is to produce a value 3 and leave no additional space for any other item (cap-item3.size=0). From row2, we already have a value 4 by using only the first two items (maxValueMat[2][4]=4). Adding item3 doesn't improve the maximum value for the capacity, and so we retain the existing value :
maxValueMat[3][4] = maxValueMat[2][4] = 4
With cap=6, adding item3 contributes value 3 and leaves 2 units of space, sufficient to add item1. The total :
item3.value + maxValueMat[2][2]=4
is not an improvement on the existing maximum value of 5 (maxValueMat[2][6]), which we derived in row 2 by using only the first two items, and so we again retain the value from row2 :
maxValueMat[3][6] = maxValueMat[2][6]=5
When cap=7, adding item3 leaves 3 units of additional space. Using the maximum value for capacity 3(maxValueMat[2][3]=4) from row2, we have a new value 7, which is greater than the value 5, derived from using only first two items :
After completing all of the entries in row3, we have :
You have now seen all of the elements of the algorithm. In general, for row i, computing maxValueMat[i][cap] involves determining whether itemi should be part of the subset of items from set {item1, item2, ... itemi} that produces the maximum value for the specified capacity. First, test whether the new item fits in the space :
- if (cap - item3.space >=0)
- testMax = itemi.value + maxValueMat[i-1][cap - itemi.size];
- // if new item increase value, use new value for matrix entry
- if(testMax > maxValueMat[i-1][cap])
- maxValueMat[i][cap] = testMax;
- else
- // retain maximum value provided by previous items
- maxValueMat[i][cap] = maxValue[i-1][cap];
The Knapsack Class :
The class Item describes the items in the knapsack. Two integer variables define the size and value of an object. To simplify access, we declare the members public. A constructor creates an instance of the class using two arguments for the size and value.
The Knapsack class includes an Item array called itemList and the integer matrix (2-dimensional array) maxValueMat as instance variables, along with integer variables for the capacity and the number of items. The constructor takes a list of Item objects and a capacity as arguments and initializes the corresponding instance variables. The constructor also allocates space for the knapsack matrix. The private method buildMaxValueMat() implements the dynamic programming version of the knapsack algorithm. For output, the method displayKnapsack() displays the maximum value and the list of the items that fit into the knapsack to produce the value. The display also notes the amount of unused space :
- Building the Knapsack Matrix
We build the [row][column] entries in maxValueMat one element at a time. To simplify the calculations, all of the entries in row 0 have value 0. The outer loop uses the control variable i to scan the items in the row range 1... numItems. A inner loop uses the control variable cap to compute the column values in the range 0 ... capacity. For each entry maxValueMat[i][cap], we use the value from the previous row as its initial value.
- // initially assume the max value for capacity
- // cap is produced by using items from 1 to i-1
- maxValueMat[i][cap] = maxValueMat[i-1][cap];
- Identifying the Items
The matrix maxValueMat not only determines the maximum value for the specified capacity, it also provides information that will allow us to determine the items that fill the knapsack. The maximum value is maxValueMat[numItems][capacity], which is an entry in the last row of the matrix. Starting with this entry, we can work back through the matrix to discover the items in the knapsack. To understand the algorithm, recall how we built the matrix. In row i,maxValueMat[i][cap] is not equal to maxValueMax[i-1][cap] only if adding itemList[i] increases the value. This becomes the criterion to determine whether itemList[i] is in the knapsack.
Let us return to our example and look at maxValueMat for the capacity 12. The solution to the problem is maxValueMat[5][12]=14.
Because maxValueMat[4][12]=13 (!=maxValueMat[5][12]), itemList[5] with size 6 and value 8 is in the knapsack. There are 6 units of unused space (cap-itemList[5].size) remaining, which can be filled from the sublist itemList[1]... itemList[4]. Working backwords, maxValueMat[4][6] indicates that the sublist produces value 6. Now maxValueMat[3][6]=5 (!=maxValueMat[4][6]), so the test criterion indicates that itemList[4] with size 5 and value 6 is in the knapsack. Only 1 unit of additional space remains. Because the value maxValueMat[i][1] are identically 0 for rows 3,2, and 1, we conclude that none of the corresponding items is in the knapsack. This fact is obvious; no item would fit into 1 unit of space. We conclude that the knapsack holds itemList[5] and itemList[4] and has 1 unit of unused space.
The method displayKnapsack() implements this algorithm. A loop scans the list of items in descending order and identifies an item in the knapsack when its presence adds value. The listing of the items in the knapsack includes their size and value.
- Evaluating the Knapsack Problem Solution
The running time of our bottom-up dynamic programming solution to the knapsack problem is O(nC), where n is the number of items and C is the capacity. This follows directly from the fact that the algorithm builds a matrix of size (n+1) x (C+1) that has O(nC) elements. The amount of computation depends critically on C. For instance, if C=n the algorithm is O(n^2), but if C=2^n, the algorithm has running time O(n2^n)
Supplement :
* Gossip@Caterpillar : 常見演算法 - 背包問題
This message was edited 19 times. Last update was at 28/11/2010 21:58:46
