🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we will dive into the classic 0-1 Knapsack problem, a fundamental problem in combinatorial optimization. The problem is to maximize the total value of items that can be put into a knapsack with a given capacity, considering that each item can be taken or left (0-1 property).
Problem
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).
Example:
Input: val[] = {60, 100, 120}, wt[] = {10, 20, 30}, W = 50
Output: 220
Explanation: Choose the 2nd and 3rd items having weights 20 and 30. The total value we can obtain is 220.
2. Solution Steps
1. Use dynamic programming to build a 2D array dp where dp[i][w] represents the maximum value that can be obtained with the first i items and a weight limit of w.
2. For each item, decide whether to include it in the knapsack or not.
3. Update the dp table according to the decision made.
4. The answer will be in dp[n][W], where n is the number of items and W is the knapsack capacity.
3. Code Program
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] val = {60, 100, 120};
int[] wt = {10, 20, 30};
int W = 50;
System.out.println("Maximum value obtained: " + knapSack(W, wt, val, val.length));
}
// Method to solve the 0-1 Knapsack problem
public static int knapSack(int W, int[] wt, int[] val, int n) {
int[][] dp = new int[n + 1][W + 1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (wt[i - 1] <= w) {
dp[i][w] = Math.max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
}
Output:
Maximum value obtained: 220
Explanation:
For the given input, the knapSack method calculates the maximum value that can be obtained with the items {60, 100, 120} and weights {10, 20, 30}, within a weight limit of 50. The dynamic programming approach ensures that the maximum value obtained is 220, by choosing the 2nd and 3rd items, which give the maximum value without exceeding the weight limit.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment