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