JHAVÉ Java-Hosted Algorithm Visualization Environment |
| Home | Learners | Instructors | Developers | Download |
The objectives of this laboratory are the mastery of
To prepare for this lab activity, read the algorithm description and compare it with your textbook, if available.
The Knapsack problem is the classic integer linear programming problem with a single constraint. The 0-1 Knapsack problem is formulated as follows:
The ci represents the value of selecting item i for inclusion in the knapsack; in implementation the values ci will be modeled as int[] c. The ai represents the weight of item i - the weights will be modeled as int[] a in the implementation. The constant b represents the maximum weight that the knapsack is permitted to hold.
To solve this problem one looks for an idea that expresses the solution in terms of subproblems. This idea is typically expressed recursively. For the 0-1 knapsack problem, the classic approach is to solve the problem for one item at a time. Think of solving the problem for every weight 0 through b for one item at a time. In the "no item" case obviously the maximum value is 0 no matter what the weight; this takes the form of the base case for a recursive formulation. Clearly the first item cannot be placed in the knapsack until the weight reaches a1 at which point the optimal value achieved is c1. At each weight y for the item k it needs to be determined if not using the item, the value of Knap(k-1, y), is better than using the item Knap(k-1, y-ak) + ck (or ck if y = ak) at the weight y. Clearly y-ak >= 0 for item k to fit into the knapsack. Note that in the case of selecting item k for the knapsack the value of Knap(k-1, y-ak) is examined - choosing k-1 as the index of the subproblem (which yields a solution using the first k-1 items) guarantees that the item k is selected at most once.
The complete recursive formulation of the solution
Knap(k, y) = Knap(k-1, y) if y < a[k]
Knap(k, y) = max { Knap(k-1, y), Knap(k-1, y-a[k])+ c[k] } if y > a[k]
Knap(k, y) = max { Knap(k-1, y), c[k] } if y = a[k]
Knap(0, y) = 0
Implementing a dynamic programming problem solution using recursion often leads to a exponential algorithm; in this case that does not necessarily occur. This is due to the manner in which the reduction of the second parameter y is done in the recursion. The dynamic programming solution utilizes an iterative algorithm that builds a 2-dimensional matrix of size n+1 x b. The matrix has a initial row which reflects the base cases - the entries will be 0 representing the value of selecting no items to place in the knapsack for each weight y, y= 1, ..., b.
The row i entries represent solutions to the following subproblems, find the max value for the knapsack using the first i items subject to the constraint that weight in the knapsack is less than or equal to y. If i = 1, then the maximum value the knapsack can achieve is c[0] - the value of selecting the first item and this is achieved for all y >= a[0]. Recall Java begins subscripting arrays at 0.
To see how the iterative algorithm produces a solution a trace of the dynamic program is examined.Suppose a[] = [4, 3, 2, 1], c[] = [7, 5, 3, 1] and b = 6. By observation the solution to the problem yields a maximum value of 10. The solution x[] = [1, 0, 1, 0].
Notice during the trace of the algorithm that each entry represents a solution to a subproblem of the original problem. For example, the third row and fifth column entry is the maximum value of the 0-1 knapsack problem using 2 items and a maximum weight of 4.
The dynamic programming matrix with the initialization of its first row a has the form. The matrix labels are colored orange and the initialized cells in cyan.| items/weights | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | ||||||
| 2 | ||||||
| 3 | ||||||
| 4 |
The first item has a weight of 4 and appears in the solution at the column with weight 4. Thereafter, its value will exceed the value of the no items selected solution.
| items/weights | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 7 | 7 | 7 |
| 2 | ||||||
| 3 | ||||||
| 4 |
The second item has a weight of 3 and appears in the solution at the column with weight 3. It is selected for column 3 since 5 + k[1][3-3] exceeds that of knap[1][3]. Thereafter, knap[1][y] > knap[1][y-3] + 5 for the weights 4 through 6 inclusive.
| items/weights | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 7 | 7 | 7 |
| 2 | 0 | 0 | 5 | 7 | 7 | 7 |
| 3 | ||||||
| 4 |
The third item has a weight of 2 and appears first in the solution in the column with weight 2. Item 3 is selected since its value 3 + k[2][2-2] exceeds that of knap[2][2]. For the next two entries, knap[2][y] > knap[2][y-2] + 3 for y = 3 and 4 - so item 3 is not selected. For y = 5, knap[2][5] = 7 and knap[2][5-2] + 3 = 8, so item 3 is again selected. Similarly for y= 6, knap[2][6] = 7 and knap[2][6-2] + 3 = 10, so item 3 is selected.
| items/weights | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 7 | 7 | 7 |
| 2 | 0 | 0 | 5 | 7 | 7 | 7 |
| 3 | 0 | 3 | 5 | 7 | 8 | 10 |
| 4 |
The fourth item has a weight of 1 and it appears in the solution at the column with weight 1 since its value 1 + k[3][1-1] exceeds that of knap[3][1]. Thereafter, knap[3][y] >= knap[3][y-1] + 1 for the weights 2 through 6 inclusive.
| items/weights | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 7 | 7 | 7 |
| 2 | 0 | 0 | 5 | 7 | 7 | 7 |
| 3 | 0 | 3 | 5 | 7 | 8 | 10 |
| 4 | 1 | 3 | 5 | 7 | 8 | 10 |
The maximum value for this knapsack problem is in the bottom leftmost entry in the matrix, knap[4][5].
The pseudo code for the 0-1 knapsack algorithm:
Initialize first row of dynamic programming matrix to 0
For each item i in 1 .. n
For each weight y in 0..b
If y > weight of item i
the (i, y)-entry is the max {(i-1, y)-entry, (i-1, y- weight i) + value of i}
Else
IF y equals the weight of item i
the (i, y)-entry is the max {(i-1, y)-entry, value of i}
Else
the (i, y)-entry is the (i-1, y)-entry
/**
* function: knapsack 0-1
* Computes the maximum value of the knapsack
*
* Inputs: two arrays - a[], c[] and an integer b
* Output: the maximum value achieved
*
*
* @param int[] a, c, int b
*/
public int knapsack01(int[] a, int[] c, int b) {
// instantiate knap the dynamic programming matrix
int[][] knap = new int[a.length+1][b];
// initial row - solutions to the subproblems with no items selected
for (int i = 0; i < b; i++)
knap[0][i] = 0;
// process one item at a time for each weight
for (int k = 1; k <= a.length; k++)
for (int y = 1; y <= b; y++)
if (y < a[k-1])
knap[k][y-1] = knap[k-1][y-1];
else
if (y > a[k-1])
knap[k][y-1] = Math.max(knap[k-1][y-1], knap[k-1][y-1-a[k-1]] + c[k-1]);
else
knap[k][y-1] = Math.max(knap[k-1][y-1], c[k-1]);
return knap[a.length][b-1];
}
The pseudo code for finding a solution to the 0-1 knapsack problem from the dynamic programming matrix follows; the algorithm will begin at knap[k][y] where k = a.length and y = b-1. The algorithm then finds the first occurrence the uppermost entry in column b with the value knap[k][y] - if this occurs in the row j then item j is an item selected for the optimal solution to the problem. In order to set up for finding the next item, mover over a[j] collumns and up one row and then repeat the process.
While k is greater than 0 Set val = knap[k][y] While knap[k-1][y] equals val go up one row in knap - reduce k by 1 Item k is a component of the solution Reduce y by the weight of item k - move over a[k] columns go up one row in knap - reduce k by 1
/**
* function: Determine which items are selected to maximum carrying value of the knapsack
* finds an array which contains 1 in the item's slot if the item is selected and 0 otherwise
*
* Inputs: the dynamic programming matrix, the length of the second sequence, the first sequence
* Output: an array containing 1 in the item's slot if the item is selected and 0 otherwise
*
*
* @param int[][] knap, int b, int[] a
*/
public int[] findKnap(int[][] knap, int b, int[] a) {
k = a.length;
int[] soln = new int[k];
for (int j = 0; j < k; j++)
soln[j] = 0;
while (k > 0) {
int val = knap[k][b-1];
while(knap[k-1][b-1] == val)
k--;
soln[k-1] = 1;
b -= a[k-1];
k--;
}
return soln;
}
The essence of the algorithm is to locate the uppermost entry in the column for the "current" optimal value. The row that contains that entry represents an item selected for inclusion in the knapsack. Once the row j is found the remaining weight is reduced by the weight of the selected item a[j], by moving left a[j] columns and up one row, to the next item eligible for inclusion in the knapsack. The algorithm begins in the lower right corner where the maximum value resides. The algorithm continues until it reaches row zero .
Phase 1 of iteration 1 - the value 10 first occurs in row 3 - item three is selected. The skipped over entry (the one with value 10) is colored yellow and the selected entry is colored blue in the diagram below.
| items/weights | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 7 | 7 | 7 |
| 2 | 0 | 0 | 5 | 7 | 7 | 7 |
| 3 | 0 | 3 | 5 | 7 | 8 | 10 |
| 4 | 1 | 3 | 5 | 7 | 8 | 10 |
Phase 2 of iteration 1 - the algorithm now reflects the weights contained in the knapsack by moving over the weight of item 3, a[2] = 2, columns and then up one row - ending the first iteration with k = 2 and y = 3. The entry in row 3 after the reduction of weight is colored green and the entry to begin the next iteration yellow.
| items/weights | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 7 | 7 | 7 |
| 2 | 0 | 0 | 5 | 7 | 7 | 7 |
| 3 | 0 | 3 | 5 | 7 | 8 | 10 |
| 4 | 1 | 3 | 5 | 7 | 8 | 10 |
Phase 1 of iteration 2 - the the value 7 first occurs in row 1 - item one is selected. The skipped over entry is colored yellow and the selected entry is colored blue in the diagram below.
| items/weights | 1 | 2 | 3 | 4 | 5 | 6 |
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 7 | 7 | 7 |
| 2 | 0 | 0 | 5 | 7 | 7 | 7 |
| 3 | 0 | 3 | 5 | 7 | 8 | 10 |
| 4 | 1 | 3 | 5 | 7 | 8 | 10 |
Phase 2 of iteration 2 - one up leaves the algorithm in row 0 which terminates the algorithm with the solution x[] = [1, 0, 1, 0].
The visualization was designed for a particular knapsack problem. So when a different problem is chosen the Recursive Call Tree and the dynamic programming matrix may not fit the visualization window very well. Moving the image up in the window and using the zoom in feature may make for better viewing of the visualization.
For your first use of this visualization try the problem:
The visualization first displays the recursive call tree for the chosen knapsack problem.
It progresses by computing the value for each entry in the dynamic programming matrix knap; the cell or cells used in the computation of the current cell's entry are colored blue and the computed value of the current cell is colored yellow. When the current weight y <= a[j] only the cell k[j-1][y-1] is shown in blue. Once y exceeds a[j] then k[j-1][y-1-a[j]] will be shown in blue - the value of c[j] is displayed in the text below the dynamic programming matrix along with the computation.
Once the matrix is filled, the process of identifying the items selected is displayed in much the same way as described in the trace above.
You can also explore the algorithm's dynamic behavior using the algorithm visualization environment JHAVÉ. If you have not worked with JHAVÉ before, please take the time to instructions on using JHAVÉ first.