0-1 Knapsack Problem in C Using Dynamic Programming

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.

Knapsack 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


You can watch below video to learn knapsack problem easily.

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

10 thoughts on “0-1 Knapsack Problem in C Using Dynamic Programming

  1. Abhishek Nath

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

    Require of this line ???

  2. Chandru

    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!!!

    1. Rittick Ghosh

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

  3. Hans Gruenauer

    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

  4. Anushree Chatterjee

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


Leave a Reply

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