The 0/1 Knapsack problem is a classic problem in computer science that is used to determine the most profitable way to fill a knapsack of limited capacity from a set of items with values and weights.
The problem can be stated as follows: given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit, and the total value is as large as possible. The constraint here is that each item can be included in the collection at most once (hence the name "0/1" Knapsack problem).
To solve this problem using dynamic programming, we can use a bottom-up approach by building a table that represents the maximum value that can be obtained by taking i items, with a maximum weight of j.
The steps to solve the problem using dynamic programming are as follows:
1. Initialize a table of size [N+1][W+1]. Here N is the number of items and W is the maximum weight capacity of the knapsack.
2. For each row in the table (representing increasing number of items), and for each column in the table (representing increasing weight capacity), calculate the maximum value of including the i-th item or excluding it.
3. The value of the cell [i][j] will be the maximum of two cases: - The maximum value obtained by including the i-th item and excluding it. - The maximum value obtained by excluding the i-th item and keeping the knapsack’s weight capacity same.
4. Once the table is completely filled, the value in the bottom-right corner of the table represents the maximum value that can be obtained using all the items and given weight capacity.
5. To determine which items were included in the collection, we can backtrack through the table by starting at the bottom-right corner, and examining the cells in the row and column that led to the current cell. If the value in the current cell is not equal to the value in the cell above it, then the i-th item was included in the collection. Otherwise, the i-th item was not included.
Let’s take a look at an example to illustrate the approach above.
Example: Suppose we have five items, each with a weight and a value as shown below:
| Item | Weight | Value |
|------|--------|-------|
| A | 2 | 3 |
| B | 3 | 4 |
| C | 4 | 5 |
| D | 5 | 8 |
| E | 9 | 10 |Let’s assume that the maximum weight capacity of the knapsack is 10.
To solve this problem using dynamic programming, we can follow the steps outlined above.
Step 1: Create the table.
We create a table of size [N+1][W+1] and initialize it to 0.
int[][] table = new int[N+1][W+1];Step 2: Fill the table with maximum value in each cell.
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {
if (items[i-1].weight > j) {
table[i][j] = table[i-1][j];
} else {
table[i][j] = Math.max(table[i-1][j], table[i-1][j-items[i-1].weight] + items[i-1].value);
}
}
}Step 3: Determine maximum value
The maximum value that can be obtained is given by the value in the last cell of the table:
int maxVal = table[N][W];Step 4: Determine the items in the collection.
We can backtrack through the table to determine which items were included in the collection.
int i = N;
int j = W;
while (i > 0 && maxVal > 0) {
if (maxVal != table[i-1][j]) {
System.out.println("Item " + i + " is included in the collection");
maxVal -= items[i-1].value;
j -= items[i-1].weight;
}
i--;
}The output of this code will be:
Item 2 is included in the collection
Item 3 is included in the collection
Item 4 is included in the collectionTherefore, to obtain the maximum value, we need to include items B, C, and D in the knapsack.