Introduction
The Knapsack Problem is a classic optimization problem. Imagine you are a thief with a bag (knapsack) that can only hold a certain amount of weight. You have a list of items, each with a specific weight and value. The challenge is to select items to put in your bag so that you maximize the total value without exceeding the weight capacity.
In this blog post, we will write a Java program to solve the 0/1 Knapsack Problem using a Dynamic Programming (DP) approach. Don’t worry if you’re new to programming — we’ll break everything down step by step to make it simple!
What is the 0/1 Knapsack Problem?
The “0/1” in the problem means:
- You either include an item in the knapsack (1) or don’t include it (0).
- You cannot take a fraction of an item.
For example:
- You have items with weights
[2, 3, 4]and values[4, 5, 6]. - Your knapsack can hold a maximum weight of
5. - The goal is to maximize the value you carry, without exceeding the weight.
The Dynamic Programming Approach
To solve this problem, we use a table to store the maximum value we can achieve for each possible weight capacity. The idea is to build the solution step by step.
Here’s how it works:
- We use a 2D array
dpwheredp[i][w]represents the maximum value we can get by considering the firstiitems and a knapsack capacity ofw. - For each item, we decide whether to:
- Include it in the knapsack (if its weight is less than or equal to the remaining capacity).
- Exclude it and use the best value from the previous item.
- We fill this table iteratively and get the final answer in
dp[n][capacity].
Java Program for 0/1 Knapsack
Here’s a simple implementation of the problem:
public class Knapsack {
public static void main(String[] args) {
// Step 1: Define weights, values, and capacity
int[] weights = {2, 3, 4}; // Weights of items
int[] values = {4, 5, 6}; // Values of items
int capacity = 5; // Maximum weight the knapsack can hold
// Step 2: Call the knapsack function and print the result
int maxProfit = knapsack(weights, values, capacity);
System.out.println("Maximum profit: " + maxProfit);
}
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length; // Number of items
// Step 3: Create a DP table
int[][] dp = new int[n + 1][capacity + 1];
// Step 4: Fill the DP table
for (int i = 1; i <= n; i++) { // Loop through items
for (int w = 1; w <= capacity; w++) { // Loop through weights
if (weights[i - 1] <= w) { // Can we include this item?
// Include or exclude the item
dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
// Exclude the item
dp[i][w] = dp[i - 1][w];
}
}
}
// Step 5: Return the maximum value at full capacity
return dp[n][capacity];
}
}
Breaking Down the Code
Let’s go through the program step by step.
1. Define the Inputs
int[] weights = {2, 3, 4}; // Weights of items
int[] values = {4, 5, 6}; // Values of items
int capacity = 5; // Maximum weight the knapsack can hold
- Explanation:
weightsarray represents the weight of each item.valuesarray represents the value of each item.capacityis the maximum weight the knapsack can hold.
2. Initialize the DP Table
int[][] dp = new int[n + 1][capacity + 1];
- Explanation:
dp[i][w]will store the maximum value we can achieve with the firstiitems and a capacity ofw.- We initialize the table to 0. If we don’t consider any items (
i = 0) or the knapsack capacity is 0 (w = 0), the maximum value is0.
3. Fill the DP Table
for (int i = 1; i <= n; i++) { // Loop through items
for (int w = 1; w <= capacity; w++) { // Loop through weights
if (weights[i - 1] <= w) { // Can we include this item?
dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
- Explanation:
- For each item
iand weightw, we check if we can include the item in the knapsack. - If the item’s weight is less than or equal to the current capacity (
w), we have two choices:- Exclude the item: Take the value from the previous row (
dp[i - 1][w]). - Include the item: Add the item’s value (
values[i - 1]) to the remaining capacity (dp[i - 1][w - weights[i - 1]]).
- Exclude the item: Take the value from the previous row (
- We take the maximum of these two choices.
- For each item
4. Get the Final Answer
return dp[n][capacity];
- Explanation:
- The final answer is stored in
dp[n][capacity], which represents the maximum value achievable using allnitems with a knapsack of capacitycapacity.
- The final answer is stored in
Example Walkthrough
Let’s solve the example with weights = {2, 3, 4}, values = {4, 5, 6}, and capacity = 5.
| Items | Weights | Values | Knapsack Capacity | Maximum Profit |
|---|---|---|---|---|
| Item 1 | 2 | 4 | 5 | 4 |
| Item 2 | 3 | 5 | 5 | 9 |
| Item 3 | 4 | 6 | 5 | 9 |
Output
Maximum profit: 9
Conclusion
In this post, we learned how to solve the 0/1 Knapsack Problem using a simple Java program. The program uses Dynamic Programming to build a solution step by step, ensuring we maximize the value of items in the knapsack without exceeding its weight capacity.
Here’s the full code for reference:
public class Knapsack {
public static void main(String[] args) {
int[] weights = {2, 3, 4};
int[] values = {4, 5, 6};
int capacity = 5;
int maxProfit = knapsack(weights, values, capacity);
System.out.println("Maximum profit: " + maxProfit);
}
public static int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
}
Try experimenting with different weights, values, and capacities to see how the program works. Happy coding! 😊