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.

Program for Knapsack Problem in C Using Dynamic Programming

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 |
#include<stdio.h> int max(int a, int b) { return (a > b)? a : b; } int knapSack(int W, int wt[], int val[], int n) { int i, w; int K[n+1][W+1]; 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]); else K[i][w] = K[i-1][w]; } } return K[n][W]; } int main() { int i, n, val[20], wt[20], W; printf("Enter number of items:"); scanf("%d", &n); printf("Enter value and weight of items:\n"); for(i = 0;i < n; ++i){ scanf("%d%d", &val[i], &wt[i]); } printf("Enter size of knapsack:"); scanf("%d", &W); printf("%d", knapSack(W, wt, val, n)); return 0; } |

**Output**

*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/

thanks , really a grate article.

effective programing

thanks to helpful me !!!!!!

For learning programming, Your website is the best Neeraz.

What does the val array contain?Thanks in advance

this program is not defind in the java using c

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

Require of this line ???

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

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

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

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