Knapsack Problem

The Knapsack Problem is a famous Dynamic Programming Problem that falls in the optimization category.

It derives its name from a scenario where, given a set of items with specific weights and assigned values, the goal is to maximize the value in a knapsack while remaining within the weight constraint.

Each item can only be selected once, as we don’t have multiple quantities of any item.

In the below example, the weights of different honeycombs and the values associated with them are provided. The goal is to maximize the value of honey that can be fit in the bear’s knapsack.

Example

Let’s take the example of Mary, who wants to carry some fruits in her knapsack and maximize the profit she makes. She should pick them such that she minimizes weight ( <= bag's capacity) and maximizes value.

Here are the weights and profits associated with the different fruits:

Items: { Apple, Orange, Banana, Melon }

Weights: { 2, 3, 1, 4 }

Profits: { 4, 5, 3, 7 }

Knapsack Capacity: 5

Fruits Picked by Mary:

Banana + Melon

💰Profit = 10

Banana and Melon is the best combination, as it gives us the maximum profit (10) and the total weight does not exceed the knapsack’s capacity (5).

The problem can be tackled using various approaches: brute force, top-down with memoization and bottom-up are all potentially viable approaches to take.

The latter two approaches (top-down with memoization and bottom-up) make use of Dynamic Programming. In more complex situations, these would likely be the much more efficient approaches to use.









Comments

Post a Comment

Popular posts from this blog

Java 8 : Find the number starts with 1 from a list of integers

  List<Integer> list = List. of ( 12 , 32 , 14 , 15 , 56 ); //Result->12,14,15 List<String> listString = list.stream().map(String::valueOf).collect(Collectors.toList()); List<String> result1 = listString.stream().filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result1-->" +result1); List<String> result2 = list.stream().map(x->x+ "" ).filter(x->x.startsWith( "1" )) .collect(Collectors.toList()); System. out .println( "result2-->" +result2);
Read more

Junit Mockito and Power Mockito

Mock vs Spy Both can be used to mock methods or fields. The difference is that  in mock, you are creating a complete mock or fake object while in spy, there is the real object and you just spying or stubbing specific methods of it . Mock vs InjectMock @Mock  creates a mock.  @InjectMocks  creates an instance of the class and injects the mocks that are created with the  @Mock  (or  @Spy ) annotations into this instance. Unit Testing Void Methods with Mockito and JUnit How to Test Void Methods  As we already know that our aim is to test void methods in a class. But it is also really important to understand why we test void methods.  Whenever we write unit test cases for any method, we expect a return value from the method. Generally, we use assert for checking if the method returns the value that we expect it to return, but in the case of void methods, they do not return any value. So how do we check if our method is functioning properly? Let’s...
Read more

Find Loop in a Linked List

Image
 Problem Statement In this problem, we are given a linked list with a loop. We have to find the first node of the loop in the linked list. Problem Statement Understanding Let’s try to understand the problem statement with the help of examples. Suppose the given list is: According to the problem statement, we need to find the starting node of the loop. From the linked list, we can see that there is a loop in the linked list starting at node with value 3 and containing 3 nodes 3, 5, and 7. The last node of the loop points back to the first node of the loop. As node with value 3 is the first node of the loop, so we will return 3 as output. Approach and Algorithm (Floyd’s Cycle Detection) Our approach will be simple: 1) Firstly, we have to detect the loop in the given linked list. For detecting a loop in any linked list, we know the most efficient algorithm is the  Floyd Cycle detection Algorithm . 2) In Floyd's cycle detection algorithm, we initialize 2 pointers,  slow ...
Read more