This Java program solves the 0/1 Knapsack problem using dynamic programming. The goal is to maximize the total value in a knapsack without exceeding its weight capacity, with each item being either included or excluded from the knapsack.
Java Program
public class Knapsack01 {
// Function to solve the 0/1 Knapsack problem using dynamic programming
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = values.length; // Number of items
// DP table where dp[i][j] represents the maximum value that can be obtained
// with the first i items and a knapsack capacity of j
int[][] dp = new int[n + 1][capacity + 1];
// Fill the dp table
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0; // Base case: no items or zero capacity
} else if (weights[i – 1] <= w) {
// Include the current item and maximize the value
dp[i][w] = Math.max(dp[i – 1][w], values[i – 1] + dp[i – 1][w – weights[i – 1]]);
} else {
// Exclude the current item
dp[i][w] = dp[i – 1][w];
}
}
}
// The last cell dp[n][capacity] contains the maximum value for the full knapsack
return dp[n][capacity];
}
public static void main(String[] args) {
// Example: weights and values of items, and the capacity of the knapsack
int[] weights = {10, 20, 30};
int[] values = {60, 100, 120};
int capacity = 50;
// Solve the 0/1 Knapsack problem
int maxValue = knapsack(weights, values, capacity);
System.out.println(“The maximum value that can be obtained is: ” + maxValue);
}
}
Explanation of the Program Structure
This program solves the classic 0/1 Knapsack problem using a dynamic programming approach. The problem involves a knapsack with a fixed weight capacity, and a set of items each with a specific weight and value. The goal is to determine the maximum value of items that can be placed in the knapsack without exceeding its capacity.
- knapsack function: This function implements the dynamic programming solution for the 0/1 knapsack problem. It takes three inputs: an array of item weights, an array of item values, and the capacity of the knapsack.
- Dynamic Programming Table (dp): A 2D table
dp[i][w]is used to store the maximum value that can be achieved using the firstiitems and a knapsack of capacityw. The table is filled by considering two options for each item: either include the item or exclude it, and take the maximum of these two choices. - Main logic: For each item, the algorithm checks whether the item can fit in the knapsack (i.e., its weight is less than or equal to the current capacity). If it fits, the algorithm updates the table with the maximum value by either including or excluding the item. The final result is stored in
dp[n][capacity], wherenis the total number of items. - Base case: When no items are considered or the knapsack has zero capacity, the value is zero. This is represented by initializing the first row and first column of the
dptable to zero. - main function: This function initializes a sample set of item weights, values, and the knapsack capacity. It calls the
knapsackfunction to compute and print the maximum value that can be obtained by optimally selecting items.
Step-by-Step Process:
- We initialize a 2D dynamic programming table
dpof size(n+1) x (capacity+1), wherenis the number of items, andcapacityis the maximum weight the knapsack can hold. - We iterate through each item and for each possible capacity of the knapsack (from 0 to the given capacity). For each item, we decide whether to include it or exclude it based on its weight and maximize the value accordingly.
- If the item fits into the knapsack, we update the table by taking the maximum of the value by including the item or excluding it.
- The final result is the value in the bottom-right corner of the table,
dp[n][capacity], which represents the maximum value we can obtain using all items and the full capacity of the knapsack.
Example:
Consider the following set of items:
Weights: {10, 20, 30}
Values: {60, 100, 120}
Knapsack capacity: 50
The optimal solution for this problem is to select the second and third items (weights 20 and 30, values 100 and 120), for a maximum total value of 220. The program will output:
The maximum value that can be obtained is: 220
Conclusion:
This Java program efficiently solves the 0/1 Knapsack problem using dynamic programming. The time complexity of this solution is O(n * W), where n is the number of items, and W is the knapsack’s capacity. This approach ensures that we explore all possible combinations of item inclusion and exclusion, providing an optimal solution.
