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

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/

Ajoythanks , really a grate article.

happyeffective programing

thanks to helpful me !!!!!!

Derrick GogoiFor learning programming, Your website is the best Neeraz.

HarshWhat does the val array contain?Thanks in advance

ramanareddythis program is not defind in the java using c

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

Require of this line ???

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

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

Hans GruenauerThanks 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

Anushree ChatterjeeWhat if we need to solve it using backtracking approach??

BaptisteThank you a lot for the program.

You offer me 2 bonus points on my final exam.

Love on you <3