# C Program to Solve Knapsack Problem Using Dynamic Programming

«
»
This is a C Program to solve knapsack problem. The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Here is the source code of the C program to solve knapsack problem using dynamic programming concept. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <stdio.h>`
2. ` `
3. `int max(int a, int b) { return (a > b)? a : b; }`
4. `// Returns the maximum value that can be put in a knapsack of capacity W`
5. `int knapsack(int W, int wt[], int val[], int n)`
6. `{`
7. `   int i, w;`
8. `   int K[n+1][W+1];`
9. ` `
10. `   // Build table K[][] in bottom up manner`
11. `   for (i = 0; i <= n; i++)`
12. `   {`
13. `       for (w = 0; w <= W; w++)`
14. `       {`
15. `           if (i==0 || w==0)`
16. `               K[i][w] = 0;`
17. `           else if (wt[i-1] <= w)`
18. `                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);`
19. `           else`
20. `                 K[i][w] = K[i-1][w];`
21. `       }`
22. `   }`
23. ` `
24. `   return K[n][W];`
25. `}`
26. ` `
27. `int main()`
28. `{`
29. `    int val[] = {60, 100, 120};`
30. `    int wt[] = {10, 20, 30};`
31. `    int  W = 50;`
32. `    int n = sizeof(val)/sizeof(val);`
33. `    printf("\nValue = %d", knapsack(W, wt, val, n));`
34. `    return 0;`
35. `}`

```\$ gcc knapsack.c -o knapsack
\$ ./knapsack

Value = 220```

Sanfoundry Global Education & Learning Series – 1000 C Programs. 