Knapsack Problem using Dynamic Programming in C

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.

```
#include <stdio.h>
```
```
 
```

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

// Returns the maximum value that can be put in a knapsack of capacity W

int knapsack(int W, int wt[], int val[], int n)

```
{
```
```
   int i, w;
```
```
   int K[n+1][W+1];
```
```
 
```

   // Build table K[][] in bottom up manner

```
   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 val[] = {60, 100, 120};
```
```
    int wt[] = {10, 20, 30};
```
```
    int  W = 50;
```
```
    int n = sizeof(val)/sizeof(val[0]);
```

    printf("\nValue = %d", knapsack(W, wt, val, n));

```
    return 0;
```
```
}
```

$ gcc knapsack.c -o knapsack
$ ./knapsack
 
Value = 220

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Subscribe Now: C Algorithms Newsletter | Important Subjects Newsletters

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Solve the Fractional Knapsack Problem

» Next - C Program to Emulate N Dice Roller

Next Steps:

Get Free Certificate of Merit in C Programming
Participate in C Programming Certification Contest
Become a Top Ranker in C Programming
Take C Programming Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Recommended Articles: