# Learn Dynamic Programming by Solving Knapsack Problem in Java

“A lot of problems we face in life, be it business, finance, including logistics, container ship loading, aircraft loading -these are all knapsack problems,” — Carsten Murawski

# What is Dynamic Programming?

In this article, I am going to discuss solving knapsack problems using dynamic programming. Dynamic Programming is a method for solving some types of problems in polynomial time.

Dynamic Programming solutions are faster than the exponential brute process such as recursion, and their correctness can be easily demonstrated. Before we can learn how to think dynamically about a problem, we must first understand:

- Overlapping Subproblems
- Optimal Substructure Property

If you are not familiar with these concepts, you can refer to my previous article here to learn about dynamic programming.

Getting Started with dynamic programming | by Pulsara Sandeepa | Javarevisited | Medium

After going through the above article, now you must be familiar with dynamic programming. Let’s dive into the solution to the knapsack problem.🎉

# What is Knapsack problem?💼

When given a set of items with a weight and a value, we have to determine the number of each item to include in a collection. The total weight is less than or equal to the given limit. And the total value of the items should be maximized.

It gets its name from the issue that someone with a fixed-size knapsack faces when they have to fill it with the most valuable items. The issue often occurs in resource allocation. Decision-makers must select from a collection of non-divisible projects or tasks when working under a strict budget or time constraint.

# How Knapsack problem related to Dynamic Programming?

Typically, Dynamic Programming may solve all problems involving maximizing or minimizing specific quantities, counting problems that require counting the arrangements under certain conditions, or specific probability problems.

Knapsack algorithm can be mainly divided into two types:

- The 0/1 Knapsack problem. In this type, each package can be fully taken or not taken. A passenger cannot take a fractional amount of a taken package or take a package more than once. The Dynamic Programming Approach can solve this type.
- Fractional Knapsack problem algorithm. In this type, we can break items to maximize the total value of the knapsack. The Greedy Strategy can solve this type.

In this article, we are going to discuss the 0/1 Knapsack problem. Let’s begin.

# How to Solve the Knapsack problem?

Question:There are given weights and values of n items, respectively, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Find out the maximum value subset of value[]. The sum of the weights of this subset is smaller than or equal to W. You cannot break an item. Either pick the complete item or don’t pick it (0–1 property).

weights ={ 3, 6,4, 5}

values = {2, 3, 6, 4}

W = 8 (Maximum weight that can be carried)

n = 4 ( no. of items )

So, our first step will be deciding a state for the problem after identifying that the problem is a Dynamic Programming problem.

As we know, Dynamic Programming is all about using calculated results to formulate the final result.

Our next step will be to find a relation between previous states to reach the current state. So we have to store the subproblems in a table and finally get the result.

## Steps to divide the problem into subproblems

step1:Create a table with 0 - W values on the horizontal axis and 0-n values vertical axis. ( think the table as matrix m)step2:Arrange the given weights into ascending order.step3:You can fill out the table like the below formula to calculate the answer for each sub-problem.m[i,W] = max( m[i-1,W] , v[i]+ m[i-1 , W - W[i])

So, we can get the maximum value from the last column and last row of the table. Then we have to obtain the items that we can carry.

## Steps to find the solution

step1:Set the pointer to the last row last column of the table( value = 8)step2:move the pointer upward until the value changed( Here, we have to go two cells upward) and select the weight in that row( Weight = 4)step3:Now the remaining weight is 4 (8-4). Move the pointer one cell up and go to the column where weight is 4 (value = 2)step4:Repeat step 2 and three until i =0

So as the above example, we can take the packs with weight 4 and weight 3 to get the highest value. This process will be challenging the first time, and you have to practice the steps until you understand the process.

Now let’s Go to the implementation.

# Conclusion

Here we arrived at the end of this article. So far, we learned How the 0/1 Knapsack problem solves in Dynamic Programing. I hope this article helped you to develop your knowledge about these concepts. Let’s meet with another interesting article soon.

Thank you for reading my article and Happy Learning 🙌😊

## References

Knapsack problem — Wikipedia. https://en.wikipedia.org/wiki/Knapsack_problem

0–1 Knapsack Problem | DP-10 — GeeksforGeeks. https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/