Demystifying the 0-1 knapsack problem: top solutions explained

Dynamic Solutions of Knapsack Problems

What is the knapsack problem?

Brute-force recursive solution, optimized dynamic programming solution, what to learn next.

The knapsack problem is one of the top dynamic programming interview questions for computer science.

The problem statement is:

solve knapsack problem using dynamic programming

You’re a burglar with a knapsack that can hold a total weight of capacity . You have a set of items ( n items) each with fixed weight capacities and values. The weight and value are represented in an integer array. Create a function knapsack() that finds a subset or number of these items that will maximize value but whose total weight does not exceed the given number capacity .

Knapsack Question Variants

There are two major variants of this question, fractional or 0-1 . The fractional variant allows you to break items to maximize the value in the pack. The 0-1 variant does not allow you to break items.

Another common variant is the constrained knapsack problem that restricts your program so you cannot select any item more than once. When an element is selected, the program must decide if it should place it in the pack or leave it.

At senior level interviews, you’ll encounter variants that add volume as a constrained attribute. In this case, each item also has a fixed volume, and the knapsack has a volume limit.

What skills does it test?

This problem is so popular because it tests many desired skills at once and can be altered to throw interviewees off balance. In other words, you have to really understand the logic of the problem and code. Simple memorization won’t take you far.

The optimal solution for the knapsack problem is always a dynamic programming solution. The interviewer can use this question to test your dynamic programming skills and see if you work for an optimized solution.

Another popular solution to the knapsack problem uses recursion . Interviewers may ask you to produce both a recursive and dynamic solution if they value both skill sets. This is a popular choice because interviewers can see how well you shift from a recursive to a dynamic solution.

The knapsack problem also tests how well you approach combinatorial optimization problems. This has many practical applications in the workplace, as all combinatorial optimization problems seek maximum benefit within constraints.

For example, combinatorial optimization is used in solutions like:

  • Determine the best programs to run on a limited resource cloud system
  • Optimize water distribution across a fixed pipe network
  • Automatically plan the best package delivery route
  • Optimize the company’s supply chain

You can expect this question to be asked for any role that manages or creates automated optimization software.

The most obvious solution to this problem is brute force recursive. This solution is brute-force because it evaluates the total weight and value of all possible subsets, then selects the subset with the highest value that is still under the weight limit.

While this is an effective solution, it is not optimal because the time complexity is exponential. Use this solution if you’re asked for a recursive approach. It can also be a good starting point for the dynamic solution.

Time complexity: O ( 2 n ) O(2^{n}) O ( 2 n ) , due to the number of calls with overlapping subcalls

Auxiliary space: O ( 1 ) O(1) O ( 1 ) , no additional storage is needed.

Here’s a visual representation of our algorithm.

All red item subsets exceed our pack’s capacity, light green are within capacity but are not highest value.

Explanation

Line numbers within explanation refer to the C++ version from above

On line 14 , we start from the beginning of the weight array and check if the item is within the maximum capacity. If it is, we call the knapsack() function recursively with the item and save the result in profit1 .

Then we recursively call the function, exclude the item, and save the result in the profit2 variable. On line 21 , we return the greater of profit1 and profit2

Pseudocode:

Here’s a pseudocode explanation of how this program functions.

This program contains many overlapping subproblems, but they’re calculated each time rather than stored. Repeated calculations increase runtime drastically. To avoid recalculating we can instead use dynamic programming to memoize the solution to subproblems for reuse.

Now, we’ll optimize our recursive solution through the addition of top-down dynamic programming to handle the overlapping subproblems.

Since we have two changing values ( capacity and currentIndex ) in our recursive function knapsackRecursive() , we can use a two-dimensional array to store the results of all the solved sub-problems. As mentioned above, we need to store results for every sub-array (i.e. for every possible index i ) and for every possible capacity c .

This is the optimal solution for the knapsack problem in both time and space complexity.

Time complexity: O ( N ∗ C ) O(N*C) O ( N ∗ C ) , our memoization table stores results for all subproblems and will have a maximum of N ∗ C N*C N ∗ C subproblems.

Auxiliary space: O ( N ∗ C + N ) O(N*C + N) O ( N ∗ C + N ) , O ( N ∗ C ) O(N*C) O ( N ∗ C ) space for the memoization table, and O ( N ) O(N) O ( N ) space for recursion call-stack.

Tips: During the interview, make sure to talk through your thought process with the interviewer so they can see your problem-solving skills.

To implement dynamic programming we only need to change 5 lines.

In line 9 , we create a two-dimensional array, dp , to hold the results of any solved subproblem. This allows us to use these memoized solutions later rather than recalculating the answer.

In lines 22 and 23 , we create a case that checks dp to see if the current sub-problem’s solution has already been found. If we have, we return the memoized solution and move onto the next subproblem.

In lines 38 , we calculate the maximum possible value of the bag if we include the current item in profit1 and the maximum value of the bag if we exclude the current item in profit2 . We then save the higher of these in our two-dimensional array dp .

In line 39 , we return the item that makes the highest knapsack value. This is a partial result that ends one recursive call before the next begins. Once this has occurred for all possible combinations, the first call will return the actual result.

Thanks for completing this deep dive into the 0-1 knapsack problem. Confidence with dynamic programming coding interview questions comes from practice and exposure to popular problem different variants.

As you’re preparing for your next coding interview, here are some more DP questions you’ll want to study:

  • Longest common substring problem
  • Palindrome subsequence problem
  • Fibonacci numbers problem
  • Staircase problem
  • Coin change problem

Educative’s course, Grokking Dynamic Programming Patterns for Coding Interviews , contains solutions to all these problems in multiple programming languages. Each solution has an in-depth, line-by-line solution breakdown to ensure you can expertly explain each solution to the interviewer. By the end of the course, you’ll be able to walk into dynamic programming coding interviews confident that you’re prepared for anything they can throw at you.

Happy interviewing!

Continue reading about coding interview questions

  • 6 Dynamic Programming problems for your next coding interview
  • Cracking the top 40 Facebook coding interview questions
  • The Coding Interview FAQ: preparation, evaluation, and structure

Haven’t found what you were looking for? Contact Us

What is the 0-1 knapsack problem?

The 0-1 knapsack problem refers to a situation in which, during the filling of a knapsack, items are either taken in their entirety or not taken at all. For instance, consider two items weighing 3kg and 5kg, respectively. If we choose the 5kg item, we cannot select just 1kg from it (as the item cannot be divided) — we must take the whole 5kg item.

Learn in-demand tech skills in half the time

Skill Paths

Assessments

Learn to Code

Tech Interview Prep

Generative AI

Data Science

Machine Learning

GitHub Students Scholarship

Early Access Courses

For Individuals

Try for Free

Become an Author

Become an Affiliate

Earn Referral Credits

Frequently Asked Questions

Privacy Policy

Cookie Policy

Terms of Service

Business Terms of Service

Data Processing Agreement

Copyright © 2024 Educative, Inc. All rights reserved.

Guru99

0/1 Knapsack Problem Fix using Dynamic Programming Example

Matthew Martin

What is the Knapsack Problem?

Knapsack Problem algorithm is a very helpful problem in combinatorics. In the supermarket there are n packages (n ≤ 100) the package i has weight W[i] ≤ 100 and value V[i] ≤ 100. A thief breaks into the supermarket, the thief cannot carry weight exceeding M (M ≤ 100). The problem to be solved here is: which packages the thief will take away to get the highest value?

  • Maximum weight M and the number of packages n.
  • Array of weight W[i] and corresponding value V[i].
  • Maximize value and corresponding weight in capacity.
  • Which packages the thief will take away.

Knapsack algorithm can be further divided into two types:

  • The 0/1 Knapsack problem using dynamic programming. In this Knapsack algorithm type, each package can be taken or not taken. Besides, the thief cannot take a fractional amount of a taken package or take a package more than once. This type can be solved by Dynamic Programming Approach.
  • Fractional Knapsack problem algorithm . This type can be solved by Greedy Strategy.

How to Solve Knapsack Problem using Dynamic Programming with Example

In the divide-and-conquer strategy, you divide the problem to be solved into subproblems. The subproblems are further divided into smaller subproblems. That task will continue until you get subproblems that can be solved easily. However, in the process of such division, you may encounter the same problem many times.

The basic idea of Knapsack dynamic programming is to use a table to store the solutions of solved subproblems. If you face a subproblem again, you just need to take the solution in the table without having to solve it again. Therefore, the algorithms designed by dynamic programming are very effective.

Solve Knapsack Problem using Dynamic Programming

To solve a problem by dynamic programming, you need to do the following tasks:

  • Find solutions of the smallest subproblems.
  • Find out the formula (or rule) to build a solution of subproblem through solutions of even smallest subproblems.
  • Create a table that stores the solutions of subproblems. Then calculate the solution of subproblem according to the found formula and save to the table.
  • From the solved subproblems, you find the solution of the original problem.

Analyze the 0/1 Knapsack Problem

When analyzing 0/1 Knapsack problem using Dynamic programming, you can find some noticeable points. The value of the knapsack algorithm depends on two factors:

  • How many packages are being considered
  • The remaining weight which the knapsack can store.

Therefore, you have two variable quantities.

With dynamic programming, you have useful information:

  • the objective function will depend on two variable quantities
  • the table of options will be a 2-dimensional table.

If calling B[i][j] is the maximum possible value by selecting in packages {1, 2, …, i} with weight limit j.

  • The maximum value when selected in n packages with the weight limit M is B[n][M]. In other words: When there are i packages to choose, B[i][j] is the optimal weight when the maximum weight of the knapsack is j.
  • The optimal weight is always less than or equal to the maximum weight: B[i][j] ≤ j.

For example: B[4][10] = 8. It means that in the optimal case, the total weight of the selected packages is 8, when there are 4 first packages to choose from (1st to 4th package) and the maximum weight of the knapsack is 10. It is not necessary that all 4 items are selected.

Formula to Calculate B[i][j]

Input, you define:

Formula to Calculate B[i][j]

  • M is the maximum weight that the knapsack can carry.

In the case of simply having only 1 package to choose. You calculate B[1][j] for every j: which means the maximum weight of the knapsack ≥ the weight of the 1st package

With the weight limit j, the optimal selections among packages {1, 2, …, i – 1, i} to have the largest value will have two possibilities:

  • If package i is not selected, B[i][j] is the maximum possible value by selecting among packages {1, 2, …, i – 1} with weight limit of j. You have:
  • If package i is selected (of course only consider this case when W[i] ≤ j) then B[i][j] is equal to the value V[i] of package i plus the maximum value can be obtained by selecting among packages {1, 2, …, i – 1} with weight limit (j – W[i]). That is, in terms of the value you have:

Due to the creation of B[i][j], which is the maximum possible value, B[i][j] will be the max of the above 2 values.

Basis of Dynamic Programming

So, you have to consider if it is better to choose package i or not. From there you have the recursive formula as follows:

It is easy to see B[0][j] = maximum value possible by selecting from 0 package = 0.

Calculate the Table of Options

You build a table of options based on the above recursive formula. To check if the results are correct (if not exactly, you rebuild the objective function B[i][j]). Through the creation of the objective function B[i][j] and the table of options, you will orient the tracing.

Table of options B includes n + 1 lines, M + 1 columns,

  • Firstly, filled with the basis of dynamic programming: Line 0 includes all zeros.
  • Using recursive formulas, use line 0 to calculate line 1, use line 1 to calculate line 2, etc. … until all lines are calculated.

Calculate the Table of Options

When calculating the table of options, you are interested in B[n][M] which is the maximum value obtained when selecting in all n packages with the weight limit M.

  • If B[n][M] = B[n – 1][M] then package n is not selected, you trace B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M] , you notice that the optimal selection has the package n and trace B[n – 1][M – W[n]].

Continue to trace until reaching row 0 of the table of options.

Algorithm to Look Up the Table of Options to Find the Selected Packages

Note: If B[i][j] = B[i – 1][j], the package i is not selected. B[n][W] is the optimal total value of package put into the knapsack.

Steps for tracing:

  • Step 1 : Starting from i = n, j = M.
  • Step 2 : Look in column j, up from bottom, you find the line i such that B[i][j] > B[i – 1][j]. Mark selected package i: Select [i] = true;
  • Step 3 : j = B[i][j] – W[i]. If j > 0, go to step 2, otherwise go to step 4
  • Step 4 : Based on the table of options to print the selected packages.

Function knapsackDyProg() in Java

Explanation of Knapsack code:

  • Create table B[][]. Set default value for each cell is 0.
  • Build table B[][] in bottom-up manner. Calculate the table of options with the retrieval formula.
  • Calculate B[i][j]. If you do not select package i.
  • Then evaluate: if you select package i, it will be more beneficial then reset B[i][j].
  • Trace the table from row n to row 0.
  • If you choose package n. Once select package n, can only add weight M – W[n – 1].

You have the output:

  • First Example:
  • Second Example:
  • DAA Tutorial PDF: Design and Analysis of Algorithms
  • Heap Sort Algorithm (With Code in Python and C++)
  • Kadence’s Algorithm: Largest Sum Contiguous Subarray
  • Radix Sort Algorithm in Data Structure
  • Doubly Linked List: C++, Python (Code Example)
  • Singly Linked List in Data Structures
  • Prime Factor Algorithm: C, Python Example
  • Tower of Hanoi Algorithm: Python, C++ Code

How to Use Dynamic Programming to Solve the 0/1 Knapsack Problem

The art of computer science often revolves around solving problems that are seemingly simple at first glance, but dig a little deeper and you'll find intricate challenges that demand creativity, logic, and precision. One such iconic problem is the 0/1 Knapsack Problem .

We just published a new course on the freeCodeCamp.org YouTube channel that offers a deep dive into the world of the 0/1 Knapsack Problem. You will learn how it works and discover how to build an efficient solution from scratch using C#. Gavin Lon developed this course.

The Knapsack Problem is often used as a pedagogical tool to teach two important paradigms in algorithm design: Dynamic Programming and Greedy Algorithms .

And if you're an aspiring programmer participating in job interviews, it could be a game-changer. Algorithmic interviews often touch upon optimization problems, and the strategies you'll learn here can be applied far beyond the knapsack.

Course Breakdown

  • Introduction : Set the stage with a brief overview of what to expect throughout the course. Get a taste of the problem's historical significance and its place in the grand tapestry of computer science.
  • Overview of the 0/1 Knapsack Problem : Dive into the heart of the matter. What exactly is this problem? Why is it termed "0/1"? Gavin demystifies the challenge, outlining the problem statement, its constraints, and real-world applications.
  • Code the Algorithm Using C# : Transition from theory to practice. Follow Gavin as he demonstrates how to translate the problem into code, using the robust and versatile C# language.
  • Dynamic Programming & Memoization Strategy : Here's where the magic happens. Learn about the power of Dynamic Programming, a technique to simplify complex problems by breaking them down into smaller, more manageable subproblems. Get introduced to the concept of memoization, a strategy to store and reuse previously computed results, ensuring the algorithm runs in optimal time.
  • Outputting the Items for the Knapsack in C# : It's not just about finding the maximum value—it's also about identifying which items to pack. In this section, Gavin will guide you through the process of extracting the actual items to include in the knapsack, making your solution complete.

The course is available right now, for free, on the freeCodeCamp.org YouTube channel (1-hour watch).

I'm a teacher and developer with freeCodeCamp.org. I run the freeCodeCamp.org YouTube channel.

If you read this far, thank the author to show them you care. Say Thanks

Learn to code for free. freeCodeCamp's open source curriculum has helped more than 40,000 people get jobs as developers. Get started

Pencil Programmer

C, C++, Java, Python Programming and Algorithms

0-1 Knapsack Problem using Dynamic Programming

Algorithm

Summary: In this tutorial, we will learn What is 0-1 Knapsack Problem and how to solve the 0/1 Knapsack Problem using Dynamic Programming.

Introduction to 0-1 Knapsack Problem

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible https://en.wikipedia.org/wiki/Knapsack_problem

For example , consider we are given the following 4 weights with respective values.

01 knapsack program using dynamic programming

We are also given a knapsack bag that has a total weight limit of 5 .

We have to find the number of each weight to include in the bag so that the total weight is less than or equal to 5 and the total value is as large as possible.

Note: We cannot include the faction of the item, we either include the whole single item or not.

There are multiple ways to solve the 0-1 Knapsack problem, one such method is recursion .

0-1 Knapsack Solution using Recursion (Inefficient Approach)

For each item, we have to decide whether to include it in the knapsack bag.

choose an item

To make this decision, we compare the total value of the bag when including the item with the value when not including the item.

Since for every item we have to repeat the same process, we use recursion.

The above program has two successive recursive calls within the function:

  • knapsack(n-1, KW) – Total value when not including the n th item.
  • knapsack(n-1, KW – weight[n]) – Total value when including the n th item.

This exponentially increases the time complexity of the program to O(2 n ).

We can definitely improve the efficiency of our program by incorporating other techniques.

The 0-1 Knapsack problem can be solved using the greedy method however using dynamic programming we can improve its efficiency.

0-1 Knapsack Solution using Dynamic Programming

The idea is to store the solutions of the repetitive subproblems into a memo table (a 2D array) so that they can be reused i.e., instead of knapsack(n-1, KW) , we will use memo-table[n-1, KW] .

But, what is the subproblem here?

For instance, when deciding on the 4 th item (whether to include it or not) we recursively make decisions for all the preceding items (i.e., 3 rd , 2 nd, and 1 st items) twice.

recursive calls in 01 knapsack problem

When deciding on the 3 rd item, the decisions of the preceding items are made once again, although they were computed initially while making the decision for the 4 th item.

This computation of the maximum value for the n th item is the subproblem here, which is computed repeatedly.

When calculated for the first time we store the corresponding value of Knapsack(N-1, KW) into the memo table and reuse if needed

Now the question arises, how the memo table will look like or supposed to have?

knapsack problem using Dynamic Programming

Note: The size of the memo table is  (Total number of items + 1) * (Knapsack Weight+1).

In the memo table:

  • Row –  is the number of items we can take. The first row is 0, it means no item is available. The second row is 1, it means only the 1st item is available. Similarly, Third-row is 2, it means only 1st and 2nd item are available… Forth row tells that all 4 items should be considered for computing the total value for the given knapsack weight.
  • Column – is the knapsack weight. The first column is 0, it means the knapsack bag is not available. The second column is 1. it means the value of knapsack weight is 1, therefore we can only take those items whose total weights sum up to 1. The fourth column (Last column) is 5, which is what we want, the total weight in the knapsack bag.

Each table cell stores the solution of a subproblem. For instance, memo-table[3][2] = 21 means for a knapsack bag of weight equal to 2, the maximum value that can be achieved with the first 3 items is 21.

As we have a memo table available with us, we iterate through its cells and use the previously stored values to calculate the values for the current cell.

Here is the implementation of the discussed dynamic programming solution:

The time complexity of the program is O(n 2 ) i.e, much better than the recursive solution.

How to know which item is included in the bag?

To know which item is selected for calculating total Benefit/Value, start from the last row and column index.

Go one level up and check whether the value in the upper level is smaller or not.

  • If YES, then it means that the difference is caused because of including the last item (4th item in our case). Now subtract the weight of the last (selected) item from j and repeat the same process for the resultant value of the jth column.
  • If NO, then go one level up more and check for the difference in the value. Keep going up until you see the difference in the value.

01 knapsack problem dynamic programming

In this tutorial, we learned to solve the 0-1 knapsack problem using the dynamic programming algorithm in C++ and Java programming languages.

You May Also Like:

  • Fractional Knapsack Problem using Greedy Algorithm
  • Dijkstra’s Shortest Path Algorithm
  • Matrix Chain Multiplication using Dynamic Programming
  • Rod Cutting Problem using Dynamic Programming

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Save my name, email, and website in this browser for the next time I comment.

Forgot password? New user? Sign up

Existing user? Log in

Backpack Problem

Already have an account? Log in here.

  • Bharath Challa
  • Josh Silverman

The backpack problem (also known as the "Knapsack problem") is a widely known combinatorial optimization problem in computer science. In this wiki, you will learn how to solve the knapsack problem using dynamic programming.

Introduction

The pseudo-code, applications.

The backpack problem can be stated as follows:

Given a set of different items, each one with an associated value and weight, determine which items you should pick in order to maximize the value of the items without surpassing the capacity of your backpack.

Concretely, imagine we have the following set of valued items and the given backpack.

Suppose you have a set of 5 items: First item \(\hspace{5mm}\) Second Item \(\hspace{5mm}\) Third Item \(\hspace{5mm}\) Fourth Item \(\hspace{5mm}\) Fifth Item \(\hspace{5mm}\) Value: \(\hspace{10mm}\) $5 $10 $3 $2 $3 Weight: 4 kg 8 kg 3 kg 5 kg 2 kg If your backpack's weight limit is \(10 \text{ kg},\) what is the optimal solution? That is, which items should you take with you? In this case, the solution is clear. One would take the second and the last items, obtaining a value of \($13\) while meeting the weight limit exactly. We achieve the maximum possible value without violating the problem's constraint. \(_\square\)

However, evaluating all possibilities is very unpractical in general, so we would like to know if there is a better way to approach this problem. In fact, there is, and we will see an algorithm in the next section.

Gina is traveling with Tom into the desert, and she'll be carrying all of their food. She can carry a maximum of \(9.5 \text{ kg},\) and has \(5500\text{ cm}^3\) of space to carry supplies in her bag. Gina can pick from the following collection of supplies:

\( \quad\, \) Food item - Weight / Volume / Calories

  • granola bars - 240 g / 400 cm\(^3\) / 900 calories
  • potato chips - 135 g / 400 cm\(^3\) / 650 calories
  • beef jerky - 2800 g / 1500 cm\(^3\) / 5000 calories
  • almonds - 410 g / 410 cm\(^3\) / 950 calories
  • apples - 182 g / 190 cm\(^3\) / 95 calories.

What is the largest number of calories she can bring with them, given her constraints?

Note: Gina can bring as many as she wants of each of the above items.

This problem can be solved using simple recursion and a two-dimensional array.

To begin, we should find a convenient representation for our problem and carefully define it. We can say that we have a set of \(n\) items, each item has value \(v_i\) and weight \(w_i\), and our bag has a total weight limit of \(W\).

Now we construct an \(n\times W\) table:

Each cell in the table has value \(t[i,j]\), where \(i\) represents the \(i^\text{th}\) row and \(j\) represents the \(j^\text{th}\) column.

\(t[i,j]\) is the maximum value we can get using any combination of the set of the first \(i\) items of the list without exceeding a certain weight \(j\). With this, we can already identify a recursion for our table:

Recursion for the knapsack problem: \[ t[i,j]=\begin{cases}t[i-1,j] \hspace{5pt} &\text{if} \hspace{5pt} w_i>j \\ \max\big(t[i-1,j], t[i-1,j-w_i]+v_i\big)\hspace{5pt} &\text{if} \hspace{5pt} w_i \leq j. \end{cases} \]

Let's try to interpret this recursion:

Suppose you have a certain value \(t[i-1,j]\) in your table, which means that the maximum value you can get using any combination of the first \(i-1\) items of your list and the sum of the weight of each item does not exceed \(j\). If we can do this, it's evident that we can do the same using the first \( i \) items of our list. So we find the first case of our recursion, which is pretty straightforward:

\[ t[i,j]=t[i-1,j] \hspace{5pt} \text{if} \hspace{5pt} w_i>j .\]

And how does the second case of the recursion work?

Given \(w_i \leq j\), we can say that \(t[i,j]= t[i-1,j-w_i]+v_i\) because if we can get a certain value \(t[i-1,j-w_i]\) using the first \(i-1\) items of the list, we can also add the \(i^\text{th}\) item of the list to the backpack and it will not exceed the current limit \(j\), because before we get the \(i^\text{th}\) item, the current weight is \(j-w_i\), so if we add the \(i^\text{th}\) item the current weight will become \(j-w_i+w_i=j\), so we maintain the current weight equal to the weight limit and the new value will be \(t[i-1,j-w_i]\) plus the value of the item \(v_i\), then \(t[i,j]\) becomes \( t[i-1,j-w_i]+v_i\). Nevertheless, this is not always the best option. If the value of \(t[i-1,j]\) is bigger, we will use this value instead of \(t[i-1,j-w_i]\). Remember \(t[i,j]\) only computes the maximum value, so we will always choose the best option.

Finally, the max() function evaluates what's the best option (i.e. it finds the greatest value).

To find the greatest possible value, we just have to get \(t[n,W]\) \((\)i.e. the maximum value possible using the \(n\) items of our list while the total wight is less than the capacity \(W\) of our bag\().\)

Complexity of the knapsack problem In this problem, we employ a matrix of height \(n\) and width \(W\), and our algorithm goes through each cell once, which makes \(n\times W\) operations in total. Hence the complexity of the knapsack problem is \( O(n\times W).\)

Now we will solve the first example:

You are given a set of five items \(I_1,I_2,I_3,I_4,I_5\)and each has a corresponding value and weight inside brackets \([v_i,w_i]:\) \[I_1=[5,4],\ \ I_2=[10,8],\ \ I_3=[3,3],\ \ I_4=[2,5],\ \ I_5=[3,2].\] What's the maximum possible value you can get, knowing that the knapsack's weight limit is \(10?\) Let's start filling up our table: We know that all the cells in the first row are zero, hence the following table: table2 Using the recursion, we know that \(t[1,0]=t[1,1]=t[1,2]=t[1,3]=0\). But when \(j=4,\) we have \(t[1,j]=t[1,4]=5\). This happens because at this point \(w[i]\leq j,\) the weight of the item is \(w[1]=4\) and \(j=4\), so it satisfies the condition for the second case of the recursion. We know that \[t[i-1,j]=t[0,4]=0\] and that \[ t\big[i-1,j-w[i]\big]+v_i=t[0,0]+v_i=0+5=5.\] Hence, the maximum here is \(5\), and then \(t[i,j]=t[1,4]=5\). Doing the same for \(j=5\) to \(j=10,\) we will also get \(5,\) so our table becomes as follows: table3 Now, \(i=2.\) We will keep doing the same process. Doing the calculations, we will see that \(t[2,j]=0\) from \(j=0\) to \(j=3\) and \(t[2,j]=5\) from \(j=4\) to \(j=7.\) When \(j=8,\) we have \(w[i] \leq j,\) so we will have to analyze both cases: \[ t[i-1,j]=t[1,8]=5\] and \[t\big[i-1,j-w[i]\big]+v_i=t[1,0]+v_i=0+10=10.\] The second option is the best one, so \[t[i,j]=t[2,8]=10.\] Doing the same until we finish the row, we get table4 Just keep using the recursion to fill up the third and the fourth rows until you get to the last one: table5 When you reach \(t[5,9],\) you will see \[t[i-1,j]=t[4,9]=10\] and \[ t\big[i-1,j-w[i]\big]+v_i=t[4,7]+v_i=8+3=11.\] For the last cell \[t[i-1,j]=t[4,10]=10\] and \[ t\big[i-1,j-w[i]\big]+v_i=t[4,8]+v_i=10+3=13.\] Therefore \(t[i,j]=t[5,10]=13\). This is our complete table: The maximum value we can get is \(t[n,W]=t[5,10]=13\), which can be achieved using the second and the last items. By doing this, the total weight will be \(10\) (it's equal to the capacity, which is 10) and the total value will be \(13.\) Here's a sample code you can use to solve the problem: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include <iostream> #include <cstring> /*Knapsack problem*/ //W=Backpack capacity //w[i]=i-th item's weight //v[i]=i-th item's value //Compares two values and returns the bigger one int maximum ( int a , int b ){ if ( a >= b ) return a ; else return b ; } using namespace std ; int main () { int W , v [ 100 ], w [ 100 ]; int i , j , n ; int table [ 100 ][ 10000 ]; //Reads W and the number of items n cin >> W >> n ; //Reads the weight and the value of each item for ( i = 1 ; i <= n ; i ++ ) { cin >> w [ i ] >> v [ i ]; } //Make every single cell in the first row equal to zero for ( j = 0 ; j <= W ; j ++ ) table [ 0 ][ j ] = 0 ; // Fills the table for ( i = 1 ; i <= n ; i ++ ) for ( j = 0 ; j <= W ; j ++ ){ //First case of the recursion if ( w [ i ] > j ) table [ i ][ j ] = table [ i - 1 ][ j ]; //Second case else table [ i ][ j ] = maximum ( table [ i - 1 ][ j ], table [ i - 1 ][ j - w [ i ]] + v [ i ]); } cout << " \n " ; //Shows the table for ( i = 0 ; i <= n ; i ++ ){ cout << " \n " ; for ( j = 0 ; j <= W ; j ++ ){ cout << table [ i ][ j ] << " " ; } } //Prints the answer cout << " \n Maximum value: \n " ; cout << table [ n ][ W ]; cout << " \n\n " ; return 0 ; }

Though simply stated and simply solved, the knapsack problem can be mapped directly, if not used as a prototype for numerous practical problems. Direct applications include the following:

  • a shipping company trying to pack as much package volume into a transport plane without breaking the weight capacity,
  • a professional sports team's desire to build a team that meets various statistical projections without breaking the salary cap, and
  • Soylent's need to satisfy daily nutritional requirements while maintaining a given powder volume per serving.

More interesting applications include the following:

  • Hedge fund's need to invest so as to maximize potential gains, while keeping the value at risk (VaR) below a given threshold.
  • The formation of gerrymandered political districts. Each town has a population \(p_i\), and a fraction \(f_i\) of its population that votes for party \(A\). The political group (political party A) that controls district selection wants to make a district with the quantity \(\dfrac{\sum_i p_i f_i}{\sum_ip_i}\) as large as possible while keeping the total number of people below some limit and maintaining a contiguous set of towns.

Constrained optimizations are some of the most common puzzles in managing all kinds of operations. Given the simplicity of its setup, the variety of techniques available to solve it, and its direct application to real problems, the knapsack problem is an excellent toy model and serves as a rich training ground for more advanced problems in optimality.

Problem Loading...

Note Loading...

Set Loading...

  • [email protected]

solve knapsack problem using dynamic programming

What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

FavTutor

  • Don’t have an account Yet? Sign Up

Remember me Forgot your password?

  • Already have an Account? Sign In

Lost your password? Please enter your email address. You will receive a link to create a new password.

Back to log-in

By Signing up for Favtutor, you agree to our Terms of Service & Privacy Policy.

Solve 0-1 Knapsack Problem (using Dynamic Programming)

  • Oct 25, 2023
  • 12 Minutes Read
  • By Vedanti Kshirsagar

Solve 0-1 Knapsack Problem (using Dynamic Programming)

The 0-1 Knapsack Problem is a classic combinatorial optimization problem in the field of computer science and mathematics. In this article, we will discuss the 0/1 Knapsack Problem, along with examples. The benefits, drawbacks, and uses of the 0/1 knapsack issue will also be covered in this last section. Therefore, let's begin! 

What is the 0-1 Knapsack Problem?

Imagine you have a backpack that can only hold a certain amount of weight. You have a bunch of toys that you want to take with you on a trip, but you can't take all of them because they won't fit in your backpack.

The 0/1 knapsack problem is like trying to decide which toys to bring with you. You have to choose which toys you want to bring and which toys you want to leave behind. The twist is that each toy has a different weight and value. Some toys are heavier than others, but they may also be more valuable.

The goal is to fill up your backpack with the toys that will give you the most value without making your backpack too heavy. It's like a puzzle where you have to figure out the best combination of toys to bring with you.

Formally speaking, the problem can be stated as follows:

Given a set of N items, each with a weight w(i) and a value v(i), and a knapsack with a maximum weight capacity W, select a subset of the items to include in the knapsack, such that the total weight of the selected items does not exceed W, and the total value of the selected items is maximized.

In this problem, the decision variable for each item is binary, meaning that each item can either be included in the knapsack (1) or not (0). Thus, the problem is also known as the "binary knapsack problem".

The problem can be modeled mathematically using the following objective function:

maximize: ∑(i=1 to N) v(i)x(i)

subject to: ∑(i=1 to N) w(i)x(i) <= W x(i) = {0,1} for i = 1,2,..N

where x(i) is a binary decision variable that takes a value of 1 if the item i is selected to be included in the knapsack, and 0 otherwise.

The objective function maximizes the total value of the selected items, while the constraint ensures that the total weight of the selected items does not exceed the maximum weight capacity of the knapsack.

The 0/1 Knapsack Problem is a combinatorial optimization problem, which means that there are a large number of possible combinations of items that can be selected to fill the knapsack. The problem is known to be NP-hard, which means that there is no known polynomial-time algorithm to find an exact solution for large instances of the problem.

Therefore, various approximate algorithms and heuristics are used to solve the problem, including dynamic programming, branch and bound, and genetic algorithms, among others. These algorithms can provide good solutions to the problem, although they may not always guarantee an optimal solution.

The most basic way to solve the 0/1 knapsack problem is using recursion. Let's take a look at the algorithm for doing so:

  • weights: an array of item weights
  • values: an array of item values
  • i: the index of the current item
  • j: the remaining knapsack capacity

The maximum value that can be obtained with the given items and knapsack capacity.

  • If there are no items left or the remaining knapsack capacity is zero, return 0.
  • If the weight of the current item is greater than the remaining knapsack capacity, skip the current item and move on to the next item. Return the result of recursively calling the knapsack with the remaining items and the same knapsack capacity.
  • Including the current item: add the value of the current item to the result of recursively calling the knapsack with the remaining items and the remaining knapsack capacity (i.e., subtracting the weight of the current item from the remaining capacity).
  • Skipping the current item: return the result of recursively calling the knapsack with the remaining items and the same knapsack capacity. The base case for the recursion is when there are no items left or the remaining knapsack capacity is zero. In this case, the function returns 0, as there is no more value to be gained.

The recursive algorithm explores all possible combinations of items that can be included in the knapsack, starting with the last item and moving backward. The function selects the item with the highest value that can be included without exceeding the knapsack capacity.

Note that this algorithm has a time complexity of O(2^n), where n is the number of items since it explores all possible combinations of items. This makes it inefficient for large input sizes, and dynamic programming approaches are usually used to solve the 0/1 knapsack problem more efficiently.

Here is the C++ code for the 0/1 knapsack problem:

Time Complexity: O(2^N)

Space Complexity: O(N), Required Stack Space for Recursion

In this code, weights is a vector of item weights, values is a vector of item values, i is the index of the current item, and j is the current knapsack capacity. The function returns the maximum value that can be obtained with the given items and knapsack capacity.

The base cases are when either there are no items left or the knapsack capacity is zero, in which case the maximum value is zero.

If the weight of the current item is greater than the remaining knapsack capacity, the current item cannot be included in the knapsack, so we move on to the next item by calling knapsack(weights, values, i-1, j) .

Otherwise, we have two options: include the current item and reduce the remaining capacity by its weight, or exclude the current item and move on to the next item. We choose the option that gives us the maximum value by calling max(values[i-1] + knapsack(weights, values, i-1, j-weights[i-1]), knapsack(weights, values, i-1, j)) .

To use this function, you can create vectors for the item weights and values, set the knapsack capacity, and call the knapsack function with the vectors and capacity as arguments.

Equivalent Python code for the same problem:

  • It is a well-known and well-studied problem, and there are efficient algorithms to solve it. For example, dynamic programming can solve the problem in O(N*W) time, where n is the number of items and W is the maximum weight capacity of the knapsack.
  • The problem has many real-world applications, such as resource allocation, project selection, and financial portfolio management.
  • The problem can be extended to the case where items can be split and placed in the knapsack partially, which leads to the fractional knapsack problem.

Disadvantages

  • The 0/1 Knapsack problem is an NP-hard problem, which means that there is no known polynomial time algorithm that can solve it for all cases.
  • The problem assumes that the values and weights of the items are known beforehand, which may not be the case in some real-world scenarios.
  • The problem does not take into account any constraints other than the weight capacity of the knapsack, such as budget constraints or time constraints.

Applications

  • Resource allocation: The problem can be used to allocate limited resources such as manpower, equipment, or materials to different projects or tasks while maximizing the overall value or profit.
  • Financial portfolio management: The problem can be used to select a portfolio of financial assets with limited investment funds while maximizing the expected return or minimizing the risk.
  • Cutting stock problem: The problem can be used to minimize the amount of waste material when cutting large sheets of material such as wood, glass, or metal into smaller pieces of various sizes.
  • Project selection: The problem can be used to select a set of projects to invest in, with limited resources and time, while maximizing the overall profit or benefit.
  • Knapsack packing: The problem can be used to pack a set of items of various shapes and sizes into a container of limited capacities, such as a backpack, a shipping container, or a warehouse.
  • DNA sequencing: The problem can be used to assemble a sequence of DNA fragments of varying lengths and weights while minimizing the overall sequencing cost.

Knapsack Problem Example

Moving on, let's fixate on a 0/1 knapsack problem example that will help us with further concepts:

Let's consider we have 4 objects, for each object, there's some weight and value associated with it. There's a knapsack of capacity 8.

knapsack Problem Example

The problem requires us to fill the knapsack with these objects. Can we add all the objects to the knapsack? No, since the capacity of the knapsack is 8 while the total weight of the objects given is 14.

Hence, all the objects cannot be added to this knapsack, we need to carry only a few objects such that the total value of the objects is maximized. We need to give the solution in the form of a set x to trace whether item i is included in the knapsack (marked as 1) or not included (marked as 0).

Further, we'll explore how to solve this example using dynamic programming and the greedy algorithm.

Knapsack Problem Using Dynamic Programming

Before we start exploring how to solve the knapsack problem using dynamic programming, let us first understand what dynamic programming exactly is .

What is Dynamic Programming?

Dynamic programming is a technique for solving complex problems by breaking them down into smaller, more manageable subproblems and solving each subproblem only once, saving the results and reusing them as needed. It is a bottom-up approach that starts with solving the smallest subproblems and builds up to solve the larger ones.

dynamic programming

The key idea behind dynamic programming is to avoid redundant calculations by storing the results of subproblems and using them to solve larger problems. This allows for efficient and fast computation, as many calculations are reused instead of being recalculated.

Dynamic programming is commonly used in computer science and other fields to solve optimization problems, such as the knapsack problem, shortest path problem, and maximum subarray problem, among others. It can also be applied to other types of problems, such as string matching, bioinformatics, and game theory.

Overall, dynamic programming is a powerful and versatile technique that allows for efficient and effective problem-solving in a wide range of applications.

maximize: ∑(i=1 to N) v(i)x(i) i.e. sum of their values needs to be maximized

subject to: ∑(i=1 to N) w(i)x(i) <= W i.e. sum of their weight should be less than or equal to the capacity of the knapsack.

To solve this problem using the 0/1 knapsack algorithm, you can start by creating a table with one row for each item and one column for each possible weight from 0 to the knapsack capacity (8 in this case):

knapsack program using dynamic programming 1

The cell in the row i and column j represents the maximum value that can be obtained using items 1 to i and a knapsack with a capacity j . The first row represents the case when there are no items, so the maximum value is always 0. The first column represents the case when the knapsack has no capacity, so the maximum value is always 0. vi and wi represent the values and weights of the specific objects.

Now, we start filling the table. We consider object 1 and ignore all other objects. We note that the weight of the first object is 2. The corresponding value is 10, so we fill the value '10' in table[1][2].

For the rest of the row, the capacity of the bag keeps increasing but since we are considering only one object i.e. object 1, we have nothing more to fill in the bag at that instance so we fill the same value throughout the row i.e. table[i][j]= table[i][j-1].

knapsack program using dynamic programming 2

Let's fill the 2nd and the 3rd row in the same way with logic and then deduce the formula.

For the third row, when we consider the 2nd object, we should also include the first object. Let's look at the 2nd object. The weight of the second object is 3, hence, it can be where the weight of the bag is 3. Hence we fill table[2][3] with 20 which is the value of the bag.

For the left side of the column, we fill in the value from the previous row of the column i.e. table[i][j] will be equal to table[i-1][j].

Now, for the right side of the column, as I had mentioned earlier when we consider object 2 we also need to consider object 1. The total weight of the bag when we consider both objects is 5 and the total value will be 30. So for the weight column 5 we fill in 3 i.e. table[2][5]=30. Now, all the values after column 5 for object 2 will be 30 since in that instance the maximum value it holds is 30. 

knapsack program using dynamic programming 3

 For the fourth row, we fill in the value for object 3 with weight 4 as 50 in table[3][4]. The left side of the table is filled with values from table[i-1][j]. We know that when we need to consider objects 1,2 and 3 while filling in the third row.

So when we consider objects 1 and 3 the total weight is 6 with the total value of the knapsack being 60.Further, when we consider objects 2 and 3 the total weight is 70 with the total value of the knapsack being 70. When we include all 3 the total weight is 10. Since the capacity of the knapsack is only 8 we cannot include all 3.

For the remaining vacant spaces, we fill them with the maximum value of the bag at the previous instance.

knapsack program using dynamic programming 4

To determine which items should be included in the knapsack to obtain the maximum value, you can move vertically upward then trace back through the table from the last cell to the first cell, following the path with the values that don't originate from the top.

In this case, the path is (4,8) -> (2,3)  -> (0,0). The value 80 doesn't come from the top which means this row is included. Similarly, the value 20 doesn't come from the top which means that row needs to be included. 

knapsack program using dynamic programming 6

This path indicates that objects 4 and 2 should be included in the knapsack to obtain the maximum value of 80, without exceeding the weight capacity. Here is the C++ code:

Time Complexity: O(N*W), where N is the total number of items and W is the capacity

Space Complexity: O(N*W), where N is the total number of items and W is the capacity

0/1 Knapsack Problem using the Greedy Method

The 0/1 Knapsack problem is a classic optimization problem where we have a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. The goal is to choose a subset of items that fit into the knapsack and maximize the total value of the chosen items.

A greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. However, the 0/1 Knapsack problem is not well-suited for a greedy approach , as choosing the items with the highest value-to-weight ratio at each step does not always lead to the optimal solution.

Here's an example to illustrate this:

Consider the following items:

  • object 1: weight = 2, value = 10
  • object 2: weight = 3, value = 20
  • object 3: weight = 4, value = 50
  • object 4: weight = 5, value = 60

And a knapsack with a capacity of 8.

knapsack program using greedy method

If we were to use a greedy algorithm to solve this problem, we would sort the items by the value-to-weight ratio in descending order as shown in the figure above, and then start adding the items one by one until the knapsack is full. The first item you would add will be the one with a value/weight ratio of 12.5 .i.e object 4 and then object 3 Using this approach, we would choose items 4 and 3, with a total value of 110. This is the wrong solution

However, the optimal solution would be to choose items 2 and 4, with a total value of 80. This can be seen by trying all possible combinations of items and selecting the one with the highest value that fits within the knapsack capacity using dynamic programming as seen above.

Therefore, a greedy algorithm is not always the best approach for the 0/1 Knapsack problem, and more advanced optimization techniques such as dynamic programming or branch-and-bound are usually needed to find the optimal solution.

Overall, the 0-1 Knapsack Problem is a fascinating challenge for computer scientists and mathematicians. Its applications span across industries, from finance and manufacturing to logistics and beyond, making it a perennial subject of interest and study.

solve knapsack problem using dynamic programming

FavTutor - 24x7 Live Coding Help from Expert Tutors!

solve knapsack problem using dynamic programming

About The Author

solve knapsack problem using dynamic programming

Vedanti Kshirsagar

More by favtutor blogs, rank() and dense_rank() functions in sql, tanish mallik.

solve knapsack problem using dynamic programming

What does $ mean in R? (How to Use?)

Aarthi juryala.

solve knapsack problem using dynamic programming

Wilcoxon Rank Sum Test in R (with Examples)

solve knapsack problem using dynamic programming

DEV Community

DEV Community

k1lgor

Posted on May 11, 2023

Solving the Knapsack Problem - A Guide to Dynamic Programming

Introduction.

The Knapsack problem is a well-known optimization problem in computer science. Given a set of items, each with a weight and a value, the problem is to select a subset of the items that maximizes the total value while keeping the total weight below a certain limit. The problem gets its name from the idea of packing a knapsack with items of varying sizes and values.

The Knapsack problem is a classic example of a dynamic programming problem, which means that we can solve it efficiently by breaking it down into smaller subproblems and combining the solutions to those subproblems to find the optimal solution.

Dynamic Programming Solution

The key idea behind the dynamic programming solution to the Knapsack problem is to build a table (often called a "DP table") where each cell represents the optimal value for a particular combination of items and weights. The table is initialized with zeros, and then filled in using a recursive formula.

In the recursive formula, we consider each item in turn, and for each item, we consider all possible weights up to the maximum weight. If the weight of the current item is greater than the current weight, we cannot include the item, so we simply use the value from the previous row in the table. If the weight of the current item is less than or equal to the current weight, we have a choice: we can either include the item, in which case we add its value to the value of the optimal solution for the remaining weight, or we can exclude the item, in which case we simply use the value from the previous row in the table.

After filling in the entire table, we can use it to backtrack and find the selected items that give us the maximum value. Starting from the bottom right corner of the table, we check each cell to see if its value is different from the value in the cell above it. If it is, that means we included the item corresponding to that row in the optimal solution, so we add it to our list of selected items and move to the cell in the previous row with the remaining weight.

The Python Implementation

Here is a Python implementation of the Knapsack algorithm using dynamic programming:

The knapsack function takes two arguments: a list of items, where each item is represented as a tuple of the form (weight, value) , and a maximum weight. The function returns a tuple containing the total value of the selected items and the list of selected items themselves.

We have four items with weight and values (2, 3) , (3, 4) , (4, 5) , and (5, 6) . We want to find the subset of items that maximizes the total value while keeping the total weight below 8. Running the knapsack function with these arguments gives us the following output:

This means that the optimal subset of items has a total value of 10, and consists of the items with weight and values (5, 6) and (3, 4) .

The Knapsack problem is a classic optimization problem that can be efficiently solved using dynamic programming. The key idea is to build a table that represents the optimal value for each combination of items and weights, and then fill it in using a recursive formula. The resulting table can be used to backtrack and find the selected items that give us the maximum value.

In this article, I have shown how to implement the Knapsack algorithm in Python using dynamic programming, and provided an example of how to use it. While this implementation is relatively simple, there are many variations of the Knapsack problem with different constraints and objectives, and more sophisticated algorithms may be needed to solve them efficiently.

Thank you for reading 🧑‍💻

Stay tuned for more 🚀

✌️ and logout

Buy Me A Coffee

Top comments (0)

pic

Templates let you quickly answer FAQs or store snippets for re-use.

Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink .

Hide child comments as well

For further actions, you may consider blocking this person and/or reporting abuse

scofieldidehen profile image

Are Tech Certifications Important to Have?

Scofield Idehen - Feb 14

envitab profile image

function signatures in Go

Ekemini Samuel - Feb 1

nathalia_friederichs profile image

Setting Up a PostgreSQL Environment in Docker: A Step-By-Step Guide

Nathalia Friederichs - Feb 5

yilialinn profile image

Understanding SSE(Server-Sent Events) and Its Benefits

Yilia - Feb 1

Once suspended, k1lgor will not be able to comment or publish posts until their suspension is removed.

Once unsuspended, k1lgor will be able to comment and publish posts again.

Once unpublished, all posts by k1lgor will become hidden and only accessible to themselves.

If k1lgor is not suspended, they can still re-publish their posts from their dashboard.

Once unpublished, this post will become invisible to the public and only accessible to k1lgor.

They can still re-publish the post if they are not suspended.

Thanks for keeping DEV Community safe. Here is what you can do to flag k1lgor:

k1lgor consistently posts content that violates DEV Community's code of conduct because it is harassing, offensive or spammy.

Unflagging k1lgor will restore default visibility to their posts.

DEV Community

We're a place where coders share, stay up-to-date and grow their careers.

Close

Welcome.please sign up.

By signing up or logging in, you agree to our Terms of service and confirm that you have read our Privacy Policy .

Already a member? Go to Log In

Welcome.please login.

Forgot your password

Not registered yet? Go to Sign Up

  • Introduction
  • Analyze Your Algorithm
  • Growth of a Function
  • Analyze Iterative Algorithms
  • Recurrences
  • Let's Iterate
  • Now the Recursion
  • Master's Theorem
  • Sort It Out
  • Bubble Sort
  • Count and Sort
  • Divide and Conquer
  • Binary Search
  • Dynamic Programming
  • Knapsack Problem
  • Rod Cutting
  • Coin Change
  • Backtracking
  • Knight's Tour Problem
  • Greedy Algorithm
  • Activity Selection
  • Egyptian Fraction
  • Huffman Codes
  • Minimum Spanning Tree
  • Prim's Algorithm

Knapsack Problem | Dynamic Programming

Suppose you woke up on some mysterious island and there are different precious items on it. Each item has a different value and weight. You are also provided with a bag to take some of the items along with you but your bag has a limitation of the maximum weight you can put in it. So, you need to choose items to put in your bag such that the overall value of items in your bag maximizes.

knapsack problem

This problem is commonly known as the knapsack or the rucksack problem. There are different kinds of items ($i$) and each item $i$ has a weight ($w_i$) and value ($v_i$) associated with it. $x_i$ is the number of $i$ kind of items we have picked. And the bag has a limitation of maximum weight ($W$).

knapsack problem table

So, our main task is to maximize the value i.e., $\sum_{i=1}^n {(v_ix_i)}$ (summation of the number of items taken * its value ) such that $\sum_{i=1}^n {w_ix_i} \leq W$ i.e., the weight of all the items should be less than the maximum weight.

There are different kind of knapsack problems:

  • 0-1 Knapsack Problem → In this type of knapsack problem, there is only one item of each kind (or we can pick only one). So, we are available with only two options for each item, either pick it (1) or leave it (0) i.e., $x_i \in \{0, 1\}$.
  • Bounded Knapsack Problem (BKP) → In this case, the quantity of each item can exceed 1 but can't be infinitely present i.e., there is an upper bound on it. So, $0 \leq x_i \leq c$, where c is the maximum quantity of $i$ we can take.
  • Unbounded Knapsack Problem (UKP) → Here, there is no limitation on the quantity of a specific item we can take i.e., $x_i \geq 0$.
  • Integer Knapsack Problem → When we are not available to just pick a part of an item i.e., we either take the entire item or not and can't just break the item and take some fraction of it, then it is called integer knapsack problem.
  • Fractional Knapsack Problem → Here, we can take even a fraction of any item. For example, take an example of powdered gold, we can take a fraction of it according to our need.

Some kind of knapsack problems are quite easy to solve while some are not. For example, in the fractional knapsack problem, we can take the item with the maximum $\frac{value}{weight}$ ratio as much as we can and then the next item with second most $\frac{value}{weight}$ ratio and so on until the maximum weight limit is reached.

In this particular chapter, we are going to study the 0-1 knapsack problem. So, let's get into it.

0-1 Knapsack Problem

Let's start by taking an example. Suppose we are provided with the following items:

knapsack problem table

and the maximum weight the bag can hold is 5 units i.e., $W=5$. Since it is a 0-1 knapsack problem, it means that we can pick a maximum of 1 item for each kind. Also, the problem is not a fractional knapsack problem but an integer one i.e., we can't break the items and we have to pick the entire item or leave it.

First take a case of solving the problem using brute force i.e., checking each possibility. As mentioned above, we have two options for each item i.e., either we can take it or leave it.

different combination in knapsack problem

So, there are two ways for each item and a total of n items and hence, the total possible combinations are

$$ \underbrace{2*2*2*...*2}_\text{$n$ times} = 2^n \text{ combinations} $$

So, you can see that this will take $O(2^n)$ time and we already know how bad an exponential running time is and thus there is no chance that we are going to use this as our solution.

One can also think of a solution of always taking the item with the highest $\frac{value}{weight}$ ratio first (known as greedy algorithm) but it is also not going to help here. As mentioned above, it could have helped in the case of the fractional knapsack problem. Let's first test this idea to see that it really doesn't work here.

The item with the highest $\frac{value}{weight}$ ratio is the $4^{th}$ one, so we will pick it and then the $1^{st}$ one. Now, we have a total value of $8+6 = 14$ and a total weight of $3+1 = 4$ units. We still have the space left to take more items having a total maximum weight of 1 unit but there is no such item left (each item left has a weight greater than 1), so this is what we can pick by using this technique.

greedy technique for knapsack problem

We can pick the $3^{rd}$ and the $4^{th}$ item with a total value of $9+6 = 15$ and a total weight of $4+1 = 5$ and beat the value of $14$.

So, let's find out another technique to solve this problem.

Let's say there is only the first item available for us. If its weight is within the limit of the maximum weight i.e., $w_1 \leq W$ then we will pick it otherwise, not.

Now, take the case when there are first two items available for us. If the weight of the second element is not within the limit i.e., $w_2 \gt W$, then we are not going to pick it. But if its weight is less than $W$, then we can either pick it or not. In case of picking it, the value of the second element ($v_2$) will be added to the total value and we will now decide for the optimized value we can get from the first element for $W-w_2$ weight limit and if we are not picking it, then we will decide for the first element for $W$ weight limit. To get the maximum total value, we will choose the maximum of these two cases.

selecting items in knapsack problem

Similarly, for the first three elements, we can't pick the third element if its weight is not within the limit i.e., $w_3 \gt W$ and in this case, we will be left with the weight limit $W$ and the first two items. If its weight is in the limit of the maximum weight, then we can either pick it or not. In case of picking it, the value of the third item ($v_3$) will be added to the total value and now we have to get the total optimized value of the first two elements and weight limit of $W-w_3$. In case of not picking it, we are just left with the first two elements and a weight limit of $W$. So, we will choose the maximum value from the latter two cases i.e., whether we are picking the $3^{rd}$ item or not.

selecting among 3 items in knapsack problem

Basically, we are developing a bottom-up approach to solve the problem. Let's say that we have to make a decision for the first $i$ elements to get the optimized value. Now, there can be two cases - the first that the weight of the $i^{th}$ item is greater than the weight limit i.e., $w_i \gt W$, in this case, we can't take this item at all, so we are left with first $i-1$ items and with the weight limit of $W$; the second case, when $w_i \leq W$, in this case, we will either take it or leave it.

Let's talk about the second case. If we will pick the item, we will add the value of the $i^{th}$ item ($v_i$) to the total value and then we are left with a total of first $i-1$ items and the total weight limit will reduce to $W-w_i$ for rest of the items. And if we don't pick it, even then we are left with the first $i-1$ items but the weight limit will be still $W$. And then we will choose the maximum of these two to get an optimized solution.

choosing optimal value in knapsack problem

Let's say $F(i, w)$ is a function which gives us the optimal value for the first $i$ items and weight limit $w$, so we can write $F(i, w)$ as:

$$ F(i, w) = \begin{cases} F(i-1, w), &\text{if $w_i \gt w$} \\[2ex] max\{F(i-1, w), \left(F(i-1, w-w_i) + v_i\right)\}, &\text{if $w_i \leq w$} \end{cases} $$

function tree in knapsack problem

As you can see from the picture given above, common subproblems are occurring more than once in the process of getting the final solution of the problem, that's why we are using dynamic programming to solve the problem.

As we are using the bottom-up approach, let's create the table for the above function.

Solution Table for 0-1 Knapsack Problem

table to store result in knapsack problem

The rows of the table are representing the weight limit i.e., the optimal value for each weight limit and the columns are for the items. So, the cell (i, j) of the table contains the optimal value for the first $i$ items and for a weight limit of $j$ units. Thus, we are going to find our solution in the cell (4,5) i.e., first 4 items with a weight limit of 5 units.

If the weight limit is 0, then we can't pick any item making so the total optimized value 0 in each case. This will also happen when i is 0, then also there is no item to pick and thus the optimized value will be 0 for any weight.

0 item or 0 weight will have 0 value

Now, let's start filling up the table according to the function we have derived above.

Starting from $F(1, 1)$, $w_1 = 3$ $W = 1$ $w_1 \gt W$ $F(i, W) = F(i-1, W)$ $F(1,1) = F(0, 1) = 0$

Similarly, $F(1, 2) = F(0, 2) = 0$.

filling table in knapsack problem

For $F(1, 3)$, $w_1 = 3$ and $W = 3$ $F(i, W) = max\{F(i-1, W), \left(F(i-1, W-w_i) + v_i\right)\}$ $F(1, 3) = max\{F(0, 3), \left(F(0, 0) + 8\right)\}$ $= max\{0, 8\} = 8$

step-wise table filling in knapsack problem

Similarly, $F(1, 4) = max\{F(0, 4), \left(F(0, 1) + 8\right)\}$ $= max\{0, 8\} = 8$ and so on.

step-wise table filling in knapsack problem

$F(1, 5) = max\{F(0, 5), \left(F(0, 2) + 8\right)\}$ $= max\{0, 8\} = 8$

step-wise table filling in knapsack problem

$F(2, 1)$ $w_2 \lt W$ $F(2, 1) = F(1, 1) = 0$

step-wise table filling in knapsack problem

$F(2, 2) = max\{F(1, 2), \left(F(1, 0) + 3\right)\}$ $= max\{0, 3\} = 3$

step-wise table filling in knapsack problem

$F(2, 3) = max\{F(1, 3), \left(F(1, 1) + 3\right)\}$ $= max\{8, 3\} = 8$

step-wise table filling in knapsack problem

So, you can see that we have finally got our optimal value in the cell (4,5) which is 15.

Now, let's generate the code for the same to implement the algorithm on a larger dataset.

Code for Knapsack Problem

We already discussed that we are going to use tabulation and our table is a 2D one. So, let's start by initializing a 2D matrix i.e., cost = [n+1][W+1] , where n is the total number of items and W is the maximum weight limit. Since we are starting from 0, so the size of the matrix is (n+1)x(W+1).

Also, our function is going to take values of n, W, weight matrix (wm) and value matrix(vm) as its parameters i.e., KNAPSACK-01(n, W, wm, vm) .

Our next task is to make the cost of the items with 0 weight limit or 0 items 0.

for w in 0 to W   cost[0, w] = 0 for i in 0 to n   cost[i, 0] = 0

Now, we have to iterate over the table and implement the derived formula.

for i in 1 to n       // iterating on matrix   for w in 1 to W     // iterating on matrix     if wm[i] > w     // w i > w, we can't pick it       cost[i, w] = cost[i-1, w]   // F(i,w) = F(i-1, w)     else         // we can pick the item       if vm[i]+cost[i-1, w-wm[i]] > cost[i-1, w] // comparing F(i-1, w) with F(i-1, w-w i )         cost[i, w] = vm[i] + cost[i-1, w-wm[i]]       else         cost[i, w] = cost[i-1, w]

We are first iterating over the table and then checking if we can pick the item or not if wm[i] > w . In case of not picking it, we are moving to the i-1 items with the weight limit of w cost[i, w] = cost[i-1, w] .

While picking it, we are comparing maximum of F(i-1, w) and F(i-1, w-w i ) if vm[i]+cost[i-1, w-wm[i]] > cost[i-1, w] and then proceeding accordingly.

After the completion of the table, we just have to return the cell (n,W) i.e., return cost[n, W] .

Thus, the full code can be written as:

Analysis for Knapsack Code

The analysis of the above code is simple, there are only simple iterations we have to deal with and no recursions. The first loops ( for w in 0 to W ) is running from 0 to W, so it will take $O(W)$ time. Similarly, the second loop is going to take $O(n)$ time.

Now, while iterating on the matrix, each of the statements is a constant time taking statement. And for every iteration of the first loop from 1 to n, the nested loop will be executed 1 to W times, thus it will take $O(n*W)$ time.

Also, the last statement ( return cost[n, W] ) is going to take constant time.

Since $O(nW)$ easily dominates $O(n)$ and $O(W)$, so our algorithm has a running time of $O(nW)$.

Till now, we have generated the algorithm to find the maximum value we can get from the listed items and the given weight limit but we don't yet know which items are really included in this optimal solution. So, let's take one step further and find out the items which are giving us this optimal solution.

Items Involved in Optimal Solution of Knapsack Problem

We can also get the items involved in the optimal solution by just using the cost matrix. Let's take an example where only first 3 items are available for us.

elements in knapsack problem

We can see that the optimal value for a weight limit of 5 units is 11. Now, take the case when only the first two elements are available, then also the optimal value is 11 for the weight limit of 5 units. This means that the third item is not in our optimal solution because its value is not affecting the total optimized value.

choosing elements for knapsack problem

And this is our strategy, move vertically upward in the table and see if the cell above the current cell has the same value. If the values of both the cells are different, then only we are going to include in our optimal solution.

items in knapsack problem

Now, let's say we have rejected the third element and taken the second one (because $11 \neq 8$, so second item will be in the solution). As we have picked the second item, our weight limit is reduced from $5$ to $5-w_2$ = $5-2$ = $3$. So, now we will move to the column of weight limit 3 and do the same thing.

Here, the first item and the 0 th items have different values, so we will include the first item.

So, we ended up by picking the first and the second items having a total weight of $3+2 = 5$ and a total value of $8+3 = 11$.

Similarly, we can do the same thing for our problem.

Items in optimal solution of knapsack problem

Code for Items in Optimal Solution

We can start iterating the matrix backward from the cell (n,W) because this cell has the optimal solution and then compare it with the cell vertically upward i.e., cost[i, j] == cost[i-1, j] . If they are not equal, then we will print it and reduce the weight limit j-wm[i] and also move one row upward i = i-1 . Otherwise, we will just move upward.

if cost[i, j] != cost[i-1, j]   print i   j = j-wm[i]   i = i-1 else   i - i-1 //don't include item, just move upward

Thus, the entire code can be written as:

You might have already noticed that with each chapter, we are digging deeper into algorithms. So, let's move to the next chapter and make our knowledge even deeper.

BlogsDope App

  • 90% Refund @Courses
  • Data Structure
  • Analysis of Algorithms
  • Backtracking
  • Dynamic Programming
  • Divide and Conquer
  • Geometric Algorithms
  • Mathematical Algorithms
  • Pattern Searching
  • Bitwise Algorithms
  • Branch & Bound
  • Randomized Algorithms

Related Articles

  • Solve Coding Problems

Introduction to Knapsack Problem, its Types and How to solve them

Fractional knapsack.

  • Fractional Knapsack Problem
  • Fractional Knapsack Queries
  • Difference between 0/1 Knapsack problem and Fractional Knapsack problem

0/1 Knapsack

  • 0/1 Knapsack Problem
  • Printing Items in 0/1 Knapsack
  • 0/1 Knapsack Problem to print all possible solutions
  • 0-1 knapsack queries
  • 0/1 Knapsack using Branch and Bound
  • 0/1 Knapsack using Least Cost Branch and Bound
  • Unbounded Fractional Knapsack
  • Unbounded Knapsack (Repetition of items allowed)
  • Unbounded Knapsack (Repetition of items allowed) | Efficient Approach
  • Double Knapsack | Dynamic Programming

Some Problems of Knapsack problem

  • Partition problem | DP-18
  • Count of subsets with sum equal to X
  • Length of longest subset consisting of A 0s and B 1s from an array of strings
  • Breaking an Integer to get Maximum Product
  • Find minimum number of coins to make a given value (Coin Change)
  • Count number of coins required to make a given value (Coin Change II)
  • Maximum sum of values of N items in 0-1 Knapsack by reducing weight of at most K items in half

The Knapsack problem is an example of the combinational optimization problem. This problem is also commonly known as the “ Rucksack Problem “. The name of the problem is defined from the maximization problem as mentioned below:

Given a bag with maximum weight capacity of W and a set of items, each having a weight and a value associated with it. Decide the number of each item to take in a collection such that the total weight is less than the capacity and the total value is maximized.

Types of Knapsack Problem:

The knapsack problem can be classified into the following types:

  • Bounded Knapsack Problem
  • Unbounded Knapsack Problem

1. Fractional Knapsack Problem

The Fractional Knapsack problem can be defined as follows:

Given the weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In Fractional Knapsack, we can break items for maximizing the total value of the knapsack.

Some practice problems on 0/1 Knapsack:

2. 0/1 Knapsack Problem

The 0/1 Knapsack problem can be defined as follows:

We are given N items where each item has some weight ( w i ) and value ( v i ) associated with it. We are also given a bag with capacity W . The target is to put the items into the bag such that the sum of values associated with them is the maximum possible. Note that here we can either put an item completely into the bag or cannot put it at all.

Mathematically the problem can be expressed as:

Maximize   subject to   and x i ∈ {0, 1}

Following are the differences between the 0/1 knapsack problem and the Fractional knapsack problem .

3. bounded knapsack problem.

The Bounded Knapsack problem can be defined as follows:

Given N items, each item having a given weight w i and a value v i , the task is to maximize the value by selecting a maximum of K items adding up to a maximum weight W .
Maximize   subject to   and x i ∈ {0, 1, . . . , K}

Some practice problems on Bounded Knapsack:

4. Unbounded Knapsack Problem

The Unbounded Knapsack problem can be defined as follows:

Given a knapsack weight W and a set of N items with certain value v i and weight w i , we need to calculate the maximum amount that could make up this quantity exactly. This is different from 0/1 Knapsack problem , here we are allowed to use an unlimited number of instances of an item.
Maximize   subject to   and   and x i ≥ 0.

Some practice problems on Unbounded Knapsack:

Variations of Knapsack Problem :

There are several variations possible for the Knapsack Problem. Some of the well-known variations are provided below:

1. Multi-objective Knapsack problem:

In this variation, the goal of filling the knapsack changes. Instead of maximizing only the value, there can be several other objectives.

For example: Consider you are organizing a music show in a hall that has a capacity of 10,000. You are organizing a show and the size of the audience depends on the popularity of the singers. Also, the more popular the singer is, the more the fee. You want to maximize the profit and minimize the amount spend on the singer simultaneously and also want to bring as many singers as possible.

2. Multi-dimensional Knapsack problem:

In this variation of the problem, the weight of any item i is given by an M dimensional vector {w i1 , w i2 , . . . w iM } and similarly, the capacity of the knapsack is also an M dimensional vector {W 1 , W 2 , . . . , W M }.

3. Multiple Knapsack problem:

This variation of the knapsack problem is similar to the Bin Packing algorithm . The difference in both the problem is here we can pick a subset of the items whereas, in the Bin Packing problem, we have to pack all the items in any of the bins. The idea is that there are multiple knapsacks which may seem like adding capacity to the initial knapsack, but it is not similar to that at all.

  • Double Knapsack

4. Quadratic Knapsack problem:

This variation has the goal of achieving the maximum value of a quadratic objective function that is subjected to binary and linear capacity constraints.

5. Geometric Knapsack problem:

In this variation, there is a set of rectangles with different values and a rectangular knapsack. The goal is to pack the largest possible value into the knapsack.

Applications of the Knapsack Problem:

The Knapsack problem has several real-life applications. Some of them are mentioned here:

  • One of the early applications of the Knapsack problem was in construction and scoring of exams in which the test takers have a choice as to which questions they answer.
  • The subset sum problem is solved using the concept of the Knapsack problem.
  • The multiple objective variations of the Knapsack problem is frequently used for transportation logistics optimization problems.
  • The multiple knapsack problem is often used in many loading and scheduling algorithms in Operational Research.

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule. Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

  • DSA in Java
  • DSA in Python
  • DSA in JavaScript

Please Login to comment...

  • Apple's New AI-powered Tool: Editing Through Text Prompts
  • Rebranding Google Bard to Gemini: All You Need to Know, Android App and Advanced subscriptions
  • Youtube TV's Multiview Update: Tailor Your Experience in 4 Easy Steps
  • Kore.ai Secures $150 Million for AI-Powered Growth
  • 10 Best IPTV Service Provider Subscriptions

Improve your Coding Skills with Practice

 alt=

What kind of Experience do you want to share?

Tutorial Playlist

Data structure tutorial, arrays in data structures: a guide with examples, all you need to know about two-dimensional arrays, all you need to know about a linked list in a data structure, the complete guide to implement a singly linked list, the ultimate guide to implement a doubly linked list, the fundamentals for understanding circular linked list.

The Ultimate Guide To Understand The Differences Between Stack And Queue

Implementing Stacks in Data Structures

Your One-Stop Solution for Stack Implementation Using Array

Your one-stop solution for queue implementation using array, your one-stop solution to learn depth-first search(dfs) algorithm from scratch, your one-stop solution for stack implementation using linked-list, the definitive guide to understand stack vs heap memory allocation, all you need to know about linear search algorithm, all you need to know about breadth-first search algorithm, a one-stop solution for using binary search trees in data structure, the best tutorial to understand trees in data structure, a complete guide to implement binary tree in data structure, a holistic look at using avl trees in data structures, all you need to know about tree traversal in data structure, the best and easiest way to understand an algorithm, the best guide you’ll ever need to understand b-tree in data structure, the best guide you'll ever need to understand spanning tree in data structure, a one-stop solution guide to understand data structure and algorithm complexity, your one-stop solution to understand shell sort algorithm, your one-stop solution to quick sort algorithm, the most useful guide to learn selection sort algorithm, everything you need to know about radix sort algorithm, everything you need to know about the counting sort algorithm, everything you need to know about the merge sort algorithm, insertion sort algorithm: one-stop solution that will help you understand insertion sort, everything you need to know about the bubble sort algorithm, the best guide you’ll ever need to understand bucket sort algorithm, your one-stop solution to understand recursive algorithm in programming, the definitive guide to understanding greedy algorithm, your one-stop solution to understand backtracking algorithm, the fundamentals of the bellman-ford algorithm, your one-stop solution for graphs in data structures, the best guide to understand and implement solutions for tower of hanoi puzzle, a simplified and complete guide to learn space and time complexity, all you need to know about the knapsack problem : your complete guide, the fibonacci series: mathematical and programming interpretation, the holistic look at longest common subsequence problem, the best article to understand what is dynamic programming, a guide to implement longest increasing subsequence using dynamic programming, a holistic guide to learn stop solution using dynamic programming, one stop solution to all the dynamic programming problems, understanding the fundamentals of binomial distribution, here’s all you need to know about minimum spanning tree in data structures, understanding the difference between array and linked list, the best article out there to understand the b+ tree in data structure, a comprehensive look at queue in data structure, your one-stop solution to understand coin change problem, the best way to understand the matrix chain multiplication problem, your one-stop solution to learn floyd-warshall algorithm for using dynamic programming, the best tutorial you'll ever need for queue implementation using linked list, how to create a fake news detection system, all you need to know about how to create a react js portfolio project, a complete guide on the role of ai in healthcare, the best guide to learn how to make a wireframe: what is a wireframe, the best dsa projects for your resume, the best guide to understanding the working and implementation of selective repeat arq, one stop guide to understanding network layer in the osi model, the working and implementation of data-link layer in the osi model, top 5 best coding books you must read, the working and implementation of physical layer in the osi model, how to create an instagram clone using react, reactjs vs vuejs, knapsack problem: 0-1 and fractional using dynamic programming.

Lesson 41 of 68

All You Need to Know About the Knapsack Problem : Your Complete Guide

Table of Contents

Knapsack dynamic programming works on the principle of using a table to store the answers to solved subproblems. If you come into a subproblem again, all you have to do is look up the answer in the table. As a result, dynamic programming-designed algorithms are incredibly efficient.

By the end of this article, you will be able to understand how to solve the problem of 0-1 and fractional knapsack using dynamic programming with the necessary details and practical implementations.

Problem Statement for the Knapsack Problem

Knapsack_Problem-statement-img1

The Knapsack Problem is used to explain both the problem and the solution. It derives its name from the limited number of things that may be carried in a fixed-size knapsack. We are given a set of items with varying weights and values; the goal is to store as much value as possible into the knapsack while staying within the weight limit.

Now, let us look at the Dynamic Programming Based Solution to Solve the problem of 0-1 Knapsack.

Want a Top Software Development Job? Start Here!

Want a Top Software Development Job? Start Here!

Dynamic Programming Based Solution to Solve the 0-1 Knapsack Problem

Knapsack_Problem-0-1-solution-img1.

We must follow the below given steps:

  • First, we will be provided weights and values of n items, in this case, six items.
  • We will then put these items in a knapsack of capacity W or, in our case, 10kg to get the maximum total value in the knapsack.
  • After putting the items, we have to fill this knapsack, but we can't break the item. So, we must either pick the entire item or skip it.
  • Sometimes this may even lead to a knapsack with some spare space left with it.

So, this is how we solve the 0-1 knapsack using dynamic programming. Now let's implement this solution through a simple C++ code.

Implement the Dynamic Programming Based Solution to Solve the 0-1 Knapsack Problem

We are given the weight of a collection of items {6, 3, 3, 2, 2, 2} and a knapsack of capacity W=10. We have to fill this knapsack, considering it as 0-1 knapsack.

// A c++ program to solve 0-1 Knapsack problem using dynamic programming

#include <bits/stdc++.h>

using namespace std;

// A function to returns a maximum of two numbers

int max(int X, int Y)

// A function to returns the maximum value

// that can be stored in a knapsack of W=10

int knapSack(int W, int wt[], int val[], int n)

vector<vector<int>> K(n + 1, vector<int>(W + 1));

// Build table K[][] in bottom up manner

for(i = 0; i <= n; i++)

for(w = 0; w <= W; w++)

if (i == 0 || w == 0)

K[i][w] = 0;

else if (wt[i - 1] <= w)

K[i][w] = max(val[i - 1] +K[i - 1][w - wt[i - 1]], K[i - 1][w]);

K[i][w] = K[i - 1][w];

return K[n][W];

int val[] = { 300, 150, 120, 100, 90, 80 };

int wt[] = { 6, 3, 3, 2, 2, 2 };

int W = 10;

int n = sizeof(val) / sizeof(val[0]);

cout << knapSack(W, wt, val, n);

Knapsack_Problem-0-1-implementation-img1

Dynamic Programming Based Solution to Solve the Fractional Knapsack Problem

Knapsack_Problem-fractional-solution-img1

We have to follow the below given steps to solve the fractional Knapsack Problem:

  • Similar to the 0-1 Knapsack Problem, we will be given weights and values of n items, in this case, six items.
  • We will put these items in a knapsack of capacity W or, in our case, 10kg to get the total maximum value in the knapsack.
  • Then, we have to fill this knapsack, but unlike 0-1 knapsack, we can even break an item to get the maximum value of the knapsack.  
  • In this case, to fill the knapsack, we will break the 3kg item into 2kg and 1kg items.

Now let's implement this solution through a simple C++ code.

Implement the Dynamic Programming Based Solution to Solve the Fractional Knapsack Problem

We will be provided with the weight of a collection of items {6, 3, 3, 2, 2, 2}. We are given a knapsack of capacity W=10 and we have to fill this knapsack, considering it as a fractional knapsack.

//A C++ program to illustrate a 

//fractional Knapsack Problem solution using dynamic programming 

// A structure to define Item

struct Item {

int val, wt;

// Constructor

Item(int val, int wt)

this->val=val;

this->wt=wt;

//A function to sort Item according to Val/wt ratio

bool cmpsort(struct Item X, struct Item Y)

double R1 = (double)X.val / (double)X.wt;

double R2 = (double)Y.val / (double)Y.wt;

return R1 > R2;

// Main greedy function to solve the problem

double fractionalKnapsack(int W, struct Item arr[], int N)

// sorting Item on basis of ratio

sort(arr, arr + N, cmpsort);

// Uncomment to see new order of Items with their

for (int i = 0; i < N; i++)

cout << arr[i].val << " " << arr[i].wt << " :

<< ((double)arr[i].val / arr[i].wt) <<

int curWt = 0; // Current weight in knapsack

double finalval = 0.0; 

// Iterating through all Items

for (int i = 0; i < N; i++) {

// If adding Item won't overflow, add it completely

if (curWt + arr[i].wt <= W) {

curWt += arr[i].wt;

finalval += arr[i].val;

// If we can't add the current Item, add fractional of it

int rem = W - curWt;

finalval += arr[i].val

* ((double)rem

/ (double)arr[i].wt);

// Returning final value

return finalval;

int W = 10; // Weight of knapsack

Item arr[] = { { 300, 6 }, { 150, 3 }, { 120, 3 }, { 100, 2 }, { 90, 2 }, { 80, 2 } };

int n = sizeof(arr) / sizeof(arr[0]);

cout << "Maximum value we can obtain = "

<< fractionalKnapsack(W, arr, n);

Knapsack_Problem-fractional-implementation-img1

With this, we have come to an end of this article. We will now look at what could be your next steps to conquer dynamic programming problems.

Advance your career as a MEAN stack developer with the  Full Stack Web Developer - MEAN Stack Master's Program . Enroll now!

Your next stop in mastering dynamic programming problems should be the Longest Common Substring Problem. The Longest Common Substring Problem involves determining the longest string which is a substring of two or more strings. There are several solutions to the problem.

If you're searching for a more in-depth understanding of software development that can help you carve out a successful career in the field, look no further. Take up Simplilearn's Postgraduate Program in Full Stack Web Development , which is offered in collaboration with Caltech CTME, the world's largest technology education institution. This Post Graduate Program will teach you how to grasp both front-end and back-end Java technologies; we will begin with the basics and move to more sophisticated Full Stack Web Development subjects. In this web development course, you'll study Angular , Spring Boot , Hibernate , JSPs, and MVC, which will help you get started as a full-stack developer. 

If you have any questions or require clarification on this "Knapsack Problem" article, please leave them in the comments section below. Our expert team will review them and respond as soon as possible.

About the Author

Vaibhav Khandelwal

Vaibhav Khandelwal is a proactive tech geek who's always on the edge of learning new technologies. He is well versed in competitive programming and possess sound knowledge of web development. He likes to read fictional and sci-fi novels and likes to play strategy games like chess.

Recommended Programs

Professional Certificate Program in Full Stack Development - MERN

Full Stack Web Developer - MEAN Stack

Automation Testing Masters Program

*Lifetime access to high-quality, self-paced e-learning content.

Recommended Resources

Implementing Stacks in Data Structures

Combating the Global Talent Shortage Through Skill Development Programs

What is MERN Stack? All You Need to Know

What is MERN Stack? All You Need to Know

The Perfect Guide for All You Need to Learn About MEAN Stack

The Perfect Guide for All You Need to Learn About MEAN Stack

The Ultimate Guide To Understand The Differences Between Stack And Queue

Skills Toolkit for the 21st Century Professional

  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.

logo

0-1 Knapsack Problem in C Using Dynamic Programming

Here you will learn about 0-1 knapsack problem in C.

If you are interested in learning more about dynamic programming techniques, AlgoMonster’s Dynamic Programming Introduction and Dynamic Programming Patterns.

We are given n items with some weights and corresponding values and a knapsack of capacity W. The items should be placed in the knapsack in such a way that the total value is maximum and total weight should be less than knapsack capacity.

In this problem 0-1 means that we can’t put the items in fraction. Either put the complete item or ignore it. Below is the solution for this problem in C using dynamic programming.

Program for Knapsack Problem in C Using Dynamic Programming

Enter number of items:3 Enter value and weight of items: 100 20 50 10 150 30 Enter size of knapsack:50 250

You can watch below video to learn knapsack problem easily.

Source:   http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/

Related Posts

Stack in c++ using linked list, singly linked list in c, linear queue in c++ using linked list, binary tree in c using recursion, 11 thoughts on “0-1 knapsack problem in c using dynamic programming”.

solve knapsack problem using dynamic programming

thanks , really a grate article.

solve knapsack problem using dynamic programming

effective programing thanks to helpful me !!!!!!

solve knapsack problem using dynamic programming

For learning programming, Your website is the best Neeraz.

solve knapsack problem using dynamic programming

What does the val array contain?Thanks in advance

solve knapsack problem using dynamic programming

this program is not defind in the java using c

solve knapsack problem using dynamic programming

int max(int a, int b) { return (a > b)? a : b; }

Require of this line ???

solve knapsack problem using dynamic programming

Hey hai , this chandru.. I need an explanation on the condition

1. Else if(wt[i-1]<=w) // this means that weight at index [i-1] is compared with index w where weight values are [20,10,30 ] and w[0 to n]..

so when comparing wt[i-1]<=w which will never be a true.. If i am right!!!

solve knapsack problem using dynamic programming

w is not from 0 to n. w is from 0 to W. here in this case w[0 to 50].

solve knapsack problem using dynamic programming

Thanks for this great tutorial. I have tried to change the code, because I need to show the selected Items, but it doesn’t work.

Maybe Someone have a solution that show the chosen items ?

Thanks for help

solve knapsack problem using dynamic programming

What if we need to solve it using backtracking approach??

solve knapsack problem using dynamic programming

Thank you a lot for the program. You offer me 2 bonus points on my final exam. Love on you <3

Leave a Comment Cancel Reply

Your email address will not be published. Required fields are marked *

Javatpoint Logo

  • Interview Q

DAA Tutorial

Asymptotic analysis, analysis of sorting, divide and conquer, lower bound theory, sorting in linear time, binary search trees, red black tree, dynamic programming, greedy algorithm, backtracking, shortest path, all-pairs shortest paths, maximum flow, sorting networks, complexity theory, approximation algo, string matching.

Interview Questions

JavaTpoint

In the above matrix, columns represent the weight, i.e., 8. The rows represent the profits and weights of items. Here we have not taken the weight 8 directly, problem is divided into sub-problems, i.e., 0, 1, 2, 3, 4, 5, 6, 7, 8. The solution of the sub-problems would be saved in the cells and answer to the problem would be stored in the final cell. First, we write the weights in the ascending order and profits according to their weights shown as below:

w i = {3, 4, 5, 6}

p i = {2, 3, 4, 1}

The first row and the first column would be 0 as there is no item for w=0

When i=1, W=1

w 1 = 3; Since we have only one item in the set having weight 3, but the capacity of the knapsack is 1. We cannot fill the item of 3kg in the knapsack of capacity 1 kg so add 0 at M[1][1] shown as below:

When i = 1, W = 2

w 1 = 3; Since we have only one item in the set having weight 3, but the capacity of the knapsack is 2. We cannot fill the item of 3kg in the knapsack of capacity 2 kg so add 0 at M[1][2] shown as below:

When i=1, W=3

w 1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack is also 3; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][3] shown as below:

When i=1, W = 4

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack is 4; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][4] shown as below:

When i=1, W = 5

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack is 5; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][5] shown as below:

When i =1, W=6

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack is 6; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][6] shown as below:

When i=1, W = 7

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack is 7; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][7] shown as below:

When i =1, W =8

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the knapsack is 8; therefore, we can fill the knapsack with an item of weight equal to 3. We put profit corresponding to the weight 3, i.e., 2 at M[1][8] shown as below:

Now the value of 'i' gets incremented, and becomes 2.

When i =2, W = 1

The weight corresponding to the value 2 is 4, i.e., w 2 = 4. Since we have only one item in the set having weight equal to 4, and the weight of the knapsack is 1. We cannot put the item of weight 4 in a knapsack, so we add 0 at M[2][1] shown as below:

When i =2, W = 2

The weight corresponding to the value 2 is 4, i.e., w 2 = 4. Since we have only one item in the set having weight equal to 4, and the weight of the knapsack is 2. We cannot put the item of weight 4 in a knapsack, so we add 0 at M[2][2] shown as below:

When i =2, W = 3

The weight corresponding to the value 2 is 4, i.e., w 2 = 4. Since we have two items in the set having weights 3 and 4, and the weight of the knapsack is 3. We can put the item of weight 3 in a knapsack, so we add 2 at M[2][3] shown as below:

When i =2, W = 4

The weight corresponding to the value 2 is 4, i.e., w 2 = 4. Since we have two items in the set having weights 3 and 4, and the weight of the knapsack is 4. We can put item of weight 4 in a knapsack as the profit corresponding to weight 4 is more than the item having weight 3, so we add 3 at M[2][4] shown as below:

When i = 2, W = 5

The weight corresponding to the value 2 is 4, i.e., w 2 = 4. Since we have two items in the set having weights 3 and 4, and the weight of the knapsack is 5. We can put item of weight 4 in a knapsack and the profit corresponding to weight is 3, so we add 3 at M[2][5] shown as below:

When i = 2, W = 6

The weight corresponding to the value 2 is 4, i.e., w 2 = 4. Since we have two items in the set having weights 3 and 4, and the weight of the knapsack is 6. We can put item of weight 4 in a knapsack and the profit corresponding to weight is 3, so we add 3 at M[2][6] shown as below:

When i = 2, W = 7

The weight corresponding to the value 2 is 4, i.e., w 2 = 4. Since we have two items in the set having weights 3 and 4, and the weight of the knapsack is 7. We can put item of weight 4 and 3 in a knapsack and the profits corresponding to weights are 2 and 3; therefore, the total profit is 5, so we add 5 at M[2][7] shown as below:

When i = 2, W = 8

Now the value of 'i' gets incremented, and becomes 3.

When i = 3, W = 1

The weight corresponding to the value 3 is 5, i.e., w 3 = 5. Since we have three items in the set having weights 3, 4, and 5, and the weight of the knapsack is 1. We cannot put neither of the items in a knapsack, so we add 0 at M[3][1] shown as below:

When i = 3, W = 2

The weight corresponding to the value 3 is 5, i.e., w 3 = 5. Since we have three items in the set having weight 3, 4, and 5, and the weight of the knapsack is 1. We cannot put neither of the items in a knapsack, so we add 0 at M[3][2] shown as below:

When i = 3, W = 3

The weight corresponding to the value 3 is 5, i.e., w 3 = 5. Since we have three items in the set of weight 3, 4, and 5 respectively and weight of the knapsack is 3. The item with a weight 3 can be put in the knapsack and the profit corresponding to the item is 2, so we add 2 at M[3][3] shown as below:

When i = 3, W = 4

The weight corresponding to the value 3 is 5, i.e., w 3 = 5. Since we have three items in the set of weight 3, 4, and 5 respectively, and weight of the knapsack is 4. We can keep the item of either weight 3 or 4; the profit (3) corresponding to the weight 4 is more than the profit corresponding to the weight 3 so we add 3 at M[3][4] shown as below:

When i = 3, W = 5

The weight corresponding to the value 3 is 5, i.e., w 3 = 5. Since we have three items in the set of weight 3, 4, and 5 respectively, and weight of the knapsack is 5. We can keep the item of either weight 3, 4 or 5; the profit (3) corresponding to the weight 4 is more than the profits corresponding to the weight 3 and 5 so we add 3 at M[3][5] shown as below:

When i =3, W = 6

The weight corresponding to the value 3 is 5, i.e., w 3 = 5. Since we have three items in the set of weight 3, 4, and 5 respectively, and weight of the knapsack is 6. We can keep the item of either weight 3, 4 or 5; the profit (3) corresponding to the weight 4 is more than the profits corresponding to the weight 3 and 5 so we add 3 at M[3][6] shown as below:

When i =3, W = 7

The weight corresponding to the value 3 is 5, i.e., w 3 = 5. Since we have three items in the set of weight 3, 4, and 5 respectively, and weight of the knapsack is 7. In this case, we can keep both the items of weight 3 and 4, the sum of the profit would be equal to (2 + 3), i.e., 5, so we add 5 at M[3][7] shown as below:

When i = 3, W = 8

The weight corresponding to the value 3 is 5, i.e., w 3 = 5. Since we have three items in the set of weight 3, 4, and 5 respectively, and the weight of the knapsack is 8. In this case, we can keep both the items of weight 3 and 4, the sum of the profit would be equal to (2 + 3), i.e., 5, so we add 5 at M[3][8] shown as below:

Now the value of 'i' gets incremented and becomes 4.

When i = 4, W = 1

The weight corresponding to the value 4 is 6, i.e., w 4 = 6. Since we have four items in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 1. The weight of all the items is more than the weight of the knapsack, so we cannot add any item in the knapsack; Therefore, we add 0 at M[4][1] shown as below:

When i = 4, W = 2

The weight corresponding to the value 4 is 6, i.e., w 4 = 6. Since we have four items in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 2. The weight of all the items is more than the weight of the knapsack, so we cannot add any item in the knapsack; Therefore, we add 0 at M[4][2] shown as below:

When i = 4, W = 3

The weight corresponding to the value 4 is 6, i.e., w 4 = 6. Since we have four items in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 3. The item with a weight 3 can be put in the knapsack and the profit corresponding to the weight 4 is 2, so we will add 2 at M[4][3] shown as below:

When i = 4, W = 4

The weight corresponding to the value 4 is 6, i.e., w 4 = 6. Since we have four items in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 4. The item with a weight 4 can be put in the knapsack and the profit corresponding to the weight 4 is 3, so we will add 3 at M[4][4] shown as below:

When i = 4, W = 5

The weight corresponding to the value 4 is 6, i.e., w 4 = 6. Since we have four items in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 5. The item with a weight 4 can be put in the knapsack and the profit corresponding to the weight 4 is 3, so we will add 3 at M[4][5] shown as below:

When i = 4, W = 6

The weight corresponding to the value 4 is 6, i.e., w 4 = 6. Since we have four items in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 6. In this case, we can put the items in the knapsack either of weight 3, 4, 5 or 6 but the profit, i.e., 4 corresponding to the weight 6 is highest among all the items; therefore, we add 4 at M[4][6] shown as below:

When i = 4, W = 7

The weight corresponding to the value 4 is 6, i.e., w 4 = 6. Since we have four items in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 7. Here, if we add two items of weights 3 and 4 then it will produce the maximum profit, i.e., (2 + 3) equals to 5, so we add 5 at M[4][7] shown as below:

When i = 4, W = 8

The weight corresponding to the value 4 is 6, i.e., w 4 = 6. Since we have four items in the set of weights 3, 4, 5, and 6 respectively, and the weight of the knapsack is 8. Here, if we add two items of weights 3 and 4 then it will produce the maximum profit, i.e., (2 + 3) equals to 5, so we add 5 at M[4][8] shown as below:

As we can observe in the above table that 5 is the maximum profit among all the entries. The pointer points to the last row and the last column having 5 value. Now we will compare 5 value with the previous row; if the previous row, i.e., i = 3 contains the same value 5 then the pointer will shift upwards. Since the previous row contains the value 5 so the pointer will be shifted upwards as shown in the below table:

Again, we will compare the value 5 from the above row, i.e., i = 2. Since the above row contains the value 5 so the pointer will again be shifted upwards as shown in the below table:

Again, we will compare the value 5 from the above row, i.e., i = 1. Since the above row does not contain the same value so we will consider the row i=1, and the weight corresponding to the row is 4. Therefore, we have selected the weight 4 and we have rejected the weights 5 and 6 shown below:

x = { 1, 0, 0}

The profit corresponding to the weight is 3. Therefore, the remaining profit is (5 - 3) equals to 2. Now we will compare this value 2 with the row i = 2. Since the row (i = 1) contains the value 2; therefore, the pointer shifted upwards shown below:

Again we compare the value 2 with a above row, i.e., i = 1. Since the row i =0 does not contain the value 2, so row i = 1 will be selected and the weight corresponding to the i = 1 is 3 shown below:

X = {1, 1, 0, 0}

The profit corresponding to the weight is 2. Therefore, the remaining profit is 0. We compare 0 value with the above row. Since the above row contains a 0 value but the profit corresponding to this row is 0. In this problem, two weights are selected, i.e., 3 and 4 to maximize the profit.

Youtube

  • Send your Feedback to [email protected]

Help Others, Please Share

facebook

Learn Latest Tutorials

Splunk tutorial

Transact-SQL

Tumblr tutorial

Reinforcement Learning

R Programming tutorial

R Programming

RxJS tutorial

React Native

Python Design Patterns

Python Design Patterns

Python Pillow tutorial

Python Pillow

Python Turtle tutorial

Python Turtle

Keras tutorial

Preparation

Aptitude

Verbal Ability

Interview Questions

Company Questions

Trending Technologies

Artificial Intelligence

Artificial Intelligence

AWS Tutorial

Cloud Computing

Hadoop tutorial

Data Science

Angular 7 Tutorial

Machine Learning

DevOps Tutorial

B.Tech / MCA

DBMS tutorial

Data Structures

DAA tutorial

Operating System

Computer Network tutorial

Computer Network

Compiler Design tutorial

Compiler Design

Computer Organization and Architecture

Computer Organization

Discrete Mathematics Tutorial

Discrete Mathematics

Ethical Hacking

Ethical Hacking

Computer Graphics Tutorial

Computer Graphics

Software Engineering

Software Engineering

html tutorial

Web Technology

Cyber Security tutorial

Cyber Security

Automata Tutorial

C Programming

C++ tutorial

Control System

Data Mining Tutorial

Data Mining

Data Warehouse Tutorial

Data Warehouse

RSS Feed

Solving 0/1 Knapsack Using Dynamic programming in Python

0:1 Knapsack

In this article, we’ll solve the 0/1 Knapsack problem using dynamic programming.

Dynamic Programming is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems .

0/1 Knapsack is perhaps the most popular problem under Dynamic Programming. It is also a great problem to learn in order to get a hang of Dynamic Programming.

In this tutorial, we will be learning about what exactly is 0/1 Knapsack and how can we solve it in Python using Dynamic Programming.

Let’s get started.

Problem Statement for 0/1 Knapsack

The problem statement of Dynamic programming is as follows :

To begin with, we have a weight array that has the weight of all the items. We also have a value array that has the value of all the items and we have a total weight capacity of the knapsack.

Given this information, we need to find the maximum value we can get while staying in the weight limit.

The problem is called 0/1 knapsack because we can either include an item as a whole or exclude it. That is to say, we can’t take a fraction of an item.

Let’s take an example to understand.

Take the following input values.

Here we get the maximum profit when we include items 1,2 and 4 giving us a total of 200 + 50 + 100 = 350.

Therefore the total profit comes out as :

How to solve 0/1 Knapsack using Dynamic Programming?

To solve 0/1 knapsack using Dynamic Programming we construct a table with the following dimensions.

The rows of the table correspond to items from 0 to n .

The columns of the table correspond to weight limit from 0 to W.

The index of the very last cell of the table would be :

Value of the cell with index [i][j] represents the maximum profit possible when considering items from 0 to i and the total weight limit as j.

After filling the table our answer would be in the very last cell of the table.

How to fill the table?

Let’s start by setting the 0th row and column to 0. We do this because the 0th row means that we have no objects and the 0th column means that the maximum weight possible is 0.

Now for each cell [i][j], we have two options :

  • Either we include object [i] in our final selection.
  • Or we don’t include object [i] in our final selection.

How do we decide whether we include object [i] in our selection?

There are two conditions that should be satisfied to include object [i] :

  • The total weight after including object [i] should not exceed the weight limit.
  • The profit after including object [i] should be greater as compared to when the object is not included.

Let’s convert our understanding of 0/1 knapsack into python code.

Python Code to solve 0/1 Knapsack

Let’s create a table using the following list comprehension method :

We will be using nested for loops to traverse through the table and fill entires in each cell.

We are going to fill the table in a bottom up manner.

Let’s breakdown the code line by line.

This part of the code is responsible for setting the 0th row and column to 0.

This line of code checks that the weight of the i(th) object is less that the total weight permissible for that cell (j).

This line of code is responsible for selecting the maximum out of the two options available to us. We can either include the object or exclude it.

Here the term table[i – 1][j] means that ith item is not included. The term val[i – 1] + table[i – 1][j – wt[i – 1]] represents that the ith item is included.

This part of the loop is accessed when the weight of ith object is greater than the permissible limit (j).

When we are done filling the table we can return the last cell of the table as the answer.

Complete code for the Knapsack solving function

The complete code for the function that solves the knapsack is given below :

Let’s try running the function for the example we took above.

Complete Code

Here’s the complete code for you to run on your system.

Upon running the code, we get the following output :

This tutorial was about solving 0/1 Knapsack using Dynamic programming in Python. We hope you had fun learning with us!

AIP Publishing Logo

  • Previous Article
  • Next Article

An improvement of dynamic programming to solve knapsack problem using multi-core system

[email protected]

  • Article contents
  • Figures & tables
  • Supplementary Data
  • Peer Review
  • Reprints and Permissions
  • Cite Icon Cite
  • Search Site

Zaidy Y. Mohammed , Mohammed W. Al-Neama; An improvement of dynamic programming to solve knapsack problem using multi-core system. AIP Conf. Proc. 25 October 2022; 2398 (1): 050007. https://doi.org/10.1063/5.0093571

Download citation file:

  • Ris (Zotero)
  • Reference Manager

The 0/1 Knapsack Problem (KP) is one of the problems in optimization where a set of items with given benefit and weights .The aim is to select a subset of the items in order to maximize the total benefit without exceeding the knapsack capacity. Nowadays, it becomes a big dilemma due to the explosion in the amount of datasets. In this paper, P(KD)P algorithm has been proposed and performed. For effectively calculating the KM matrix using multi- core system, an improved approach of the DP_KP algorithm has been considered. The proposed scheduling and partitioning approaches have accomplished a significant enhancement to the overall performance. Executions were implemented on corei7 with (8 cores). It outperforms sequential KP_DP more than 16-fold speedup and (KD)P more than 5-fold speedup. Its efficiency reaches 0.316, 0.0829 and 0.0979 over the KP_DP, (KD)P, and P(KD)P respectively.

Sign in via your Institution

Citing articles via, publish with us - request a quote.

solve knapsack problem using dynamic programming

Sign up for alerts

  • Online ISSN 1551-7616
  • Print ISSN 0094-243X
  • For Researchers
  • For Librarians
  • For Advertisers
  • Our Publishing Partners  
  • Physics Today
  • Conference Proceedings
  • Special Topics

pubs.aip.org

  • Privacy Policy
  • Terms of Use

Connect with AIP Publishing

This feature is available to subscribers only.

Sign In or Create an Account

IMAGES

  1. Dynamic Programming 0-1 Knapsack Problem Example

    solve knapsack problem using dynamic programming

  2. 0/1 Knapsack Problem

    solve knapsack problem using dynamic programming

  3. 0/1 Knapsack Problem Using Dynamic Programming

    solve knapsack problem using dynamic programming

  4. how to solve the knapsack problem with dynamic programming

    solve knapsack problem using dynamic programming

  5. solve knapsack problem using dynamic programming

    solve knapsack problem using dynamic programming

  6. [Algo 24] Solving knapsack problem using dynamic programming

    solve knapsack problem using dynamic programming

VIDEO

  1. 0/1 Knapsack Problem using Dynamic Programming || Explained in Nepali

  2. PART-1 KNAPSACK PROBLEM IN DYNAMIC PROGRAMMING

  3. 0-1 Knapsack by Dynamic programming very easy trick

  4. 43 C Program to Solve Knapsack Problem using Dynamic Programming

  5. KnapSack problem,(using Recursion),JAVA

  6. #32 Knapsack Algorithm with Example- Asymmetric key cryptography |CNS|

COMMENTS

  1. How to solve the Knapsack Problem with dynamic programming

    Solution Step 1: First, we create a 2-dimensional array (i.e. a table) of n + 1 rows and w + 1 columns. A row number i represents the set of all the items from rows 1— i. For instance, the values...

  2. 0/1 Knapsack Problem

    Recommended Practice 0 - 1 Knapsack Problem Try It! Recursion Approach for 0/1 Knapsack Problem: To solve the problem follow the below idea: A simple solution is to consider all subsets of items and calculate the total weight and profit of all subsets. Consider the only subsets whose total weight is smaller than W.

  3. Demystifying the 0-1 knapsack problem: top solutions explained

    The optimal solution for the knapsack problem is always a dynamic programming solution. The interviewer can use this question to test your dynamic programming skills and see if you work for an optimized solution. Another popular solution to the knapsack problem uses recursion.

  4. 0/1 Knapsack Problem Fix using Dynamic Programming Example

    How to Solve Knapsack Problem using Dynamic Programming with Example In the divide-and-conquer strategy, you divide the problem to be solved into subproblems. The subproblems are further divided into smaller subproblems. That task will continue until you get subproblems that can be solved easily.

  5. How to Use Dynamic Programming to Solve the 0/1 Knapsack Problem

    The Knapsack Problem is often used as a pedagogical tool to teach two important paradigms in algorithm design: Dynamic Programming and Greedy Algorithms. And if you're an aspiring programmer participating in job interviews, it could be a game-changer. Algorithmic interviews often touch upon optimization problems, and the strategies you'll learn ...

  6. 0-1 Knapsack Problem using Dynamic Programming

    There are multiple ways to solve the 0-1 Knapsack problem, one such method is recursion. 0-1 Knapsack Solution using Recursion (Inefficient Approach) For each item, we have to decide whether to include it in the knapsack bag.

  7. Solving the Knapsack Problem with Dynamic Programming

    1 Using the Master Theorem to Solve Recurrences 2 Solving the Knapsack Problem with Dynamic Programming ... 4 more parts... 7 Finding Max Flow using the Ford-Fulkerson Algorithm and Matthew McConaughey 8 Completing Georgia Tech's Online Master of Science in Computer Science What is the Knapsack Problem?

  8. Backpack Problem

    The backpack problem (also known as the "Knapsack problem") is a widely known combinatorial optimization problem in computer science. In this wiki, you will learn how to solve the knapsack problem using dynamic programming. The backpack problem can be stated as follows: Concretely, imagine we have the following set of valued items and the given backpack. However, evaluating all ...

  9. Solve 0-1 Knapsack Problem (using Dynamic Programming)

    Solve 0-1 Knapsack Problem (using Dynamic Programming) The 0-1 Knapsack Problem is a classic combinatorial optimization problem in the field of computer science and mathematics. In this article, we will discuss the 0/1 Knapsack Problem, along with examples. The benefits, drawbacks, and uses of the 0/1 knapsack issue will also be covered in this ...

  10. Solving the Knapsack Problem

    The key idea behind the dynamic programming solution to the Knapsack problem is to build a table (often called a "DP table") where each cell represents the optimal value for a particular combination of items and weights. The table is initialized with zeros, and then filled in using a recursive formula. In the recursive formula, we consider each ...

  11. Knapsack Programming Using Dynamic Programming and its Analysis

    As you can see from the picture given above, common subproblems are occurring more than once in the process of getting the final solution of the problem, that's why we are using dynamic programming to solve the problem. As we are using the bottom-up approach, let's create the table for the above function. Solution Table for 0-1 Knapsack Problem

  12. 0/1 Knapsack Problem

    Design & Analysis of Algorithms Knapsack Problem- You are given the following- A knapsack (kind of shoulder bag) with limited weight capacity. Few items each having some weight and value. The problem states- Which items should be placed into the knapsack such that- The value or profit obtained by putting the items into the knapsack is maximum.

  13. How to Solve The 0/1 Knapsack Problem Using Dynamic Programming

    1 Photo by Vitaly Vlasov from Pexels The 0/1 knapsack problem is a classical dynamic programming problem. The knapsack problem is a popular mathematical problem that has been studied...

  14. Introduction to Knapsack Problem, its Types and How to solve them

    1. Fractional Knapsack Problem The Fractional Knapsack problem can be defined as follows: Given the weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In Fractional Knapsack, we can break items for maximizing the total value of the knapsack.

  15. Knapsack Problem using Dynamic Programming

    Algorithm Knapsack Problem using Dynamic Programming by codecrucks · Published 23/11/2021 · Updated 03/08/2022 In this article, we will discuss how to solve Knapsack Problem using Dynamic Programming. We have already discussed how to solve knapsack problem using greedy approach. Knapsack Problem using Dynamic Programming

  16. Knapsack Problem: 0-1 & Fractional Using Dynamic Programming

    Dynamic Programming Based Solution to Solve the 0-1 Knapsack Problem. We must follow the below given steps: First, we will be provided weights and values of n items, in this case, six items. We will then put these items in a knapsack of capacity W or, in our case, 10kg to get the maximum total value in the knapsack.

  17. 0-1 Knapsack Problem in C Using Dynamic Programming

    0-1 Knapsack Problem in C Using Dynamic Programming 0-1 Knapsack Problem in C Using Dynamic Programming DSA / By Neeraj Mishra Here you will learn about 0-1 knapsack problem in C. If you are interested in learning more about dynamic programming techniques, AlgoMonster's Dynamic Programming Introduction and Dynamic Programming Patterns.

  18. Dynamic Programming

    The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

  19. DAA

    The 0/1 knapsack problem is solved by the dynamic programming. What is the fractional knapsack problem? The fractional knapsack problem means that we can divide the item. For example, we have an item of 3 kg then we can pick the item of 2 kg and leave the item of 1 kg. The fractional knapsack problem is solved by the Greedy approach.

  20. Solving 0/1 Knapsack Using Dynamic programming in Python

    350 How to solve 0/1 Knapsack using Dynamic Programming? To solve 0/1 knapsack using Dynamic Programming we construct a table with the following dimensions. [n + 1] [W + 1] The rows of the table correspond to items from 0 to n. The columns of the table correspond to weight limit from 0 to W. The index of the very last cell of the table would be :

  21. An improvement of dynamic programming to solve knapsack problem using

    The 0/1 Knapsack Problem (KP) is one of the problems in optimization where a set of items with given benefit and weights .The aim is to select a subset of the items in order to maximize the total benefit without exceeding the knapsack capacity. Nowadays, it becomes a big dilemma due to the explosion in the amount of datasets.

  22. Dynamic Programming Algorithms

    0-1 knapsack problem The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item. Fractional knapsack problem. Exhibit greedy choice property. Ş Greedy algorithm exists.

  23. c++

    2 Answers. First of all, you can use only one dimension to solve the knapsack problem. This will reduce your memory from dp [W] [n] (n*W space) to dp [W] (W space). You can look here: 0/1 Knapsack Dynamic Programming Optimazion, from 2D matrix to 1D matrix. But, even if you use only dp [W], your W is really high, and might be too much memory.

  24. Solving fractional knapsack problem with dynamic programming

    1 Answer Sorted by: 1 Yes, you can solve the problem with dynamic programming. Let f (i, j) denote the maximum total value that can be obtained using the first i elements using a knapsack whose capacity is j. If you are familiar with the 0-1 knapsack problem, then you may remember that we had the exact same function.