Advanced Algorithms Problems | Engineering
[1]
-
0-1 Knapsack Problem comes under Dynamic Programming Approach (DP)
-
A knapsack is a bag. And the knapsack problem deals with the putting items to the bag based on the value of the items. It aim is to maximise the value inside the bag. In 0-1 Knapsack you can either put the item or discard it, there is no concept of putting some part of item in the knapsack.
Here you will learn about 0-1 knapsack problem in C.
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.
[2]