0-1 Knapsack Problem in C

This is a C Program to solve 0-1 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 the given 0-1 knapsack problem. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
#include <stdint.h>
```
```
 
```
```
typedef struct {
```
```
        const char * name;
```
```
        int weight, value;
```
```
} item_t;
```
```
 
```
```
item_t item[] = {
```

        {"map",                     9,       150},

        {"compass",                 13,      35},

        {"water",                   153,     200},

        {"sandwich",                50,      160},

        {"glucose",                 15,      60},

        {"tin",                     68,      45},

        {"banana",                  27,      60},

        {"apple",                   39,      40},

        {"cheese",                  23,      30},

        {"beer",                    52,      10},

        {"suntancream",             11,      70},

        {"camera",                  32,      30},

        {"T-shirt",                 24,      15},

        {"trousers",                48,      10},

        {"umbrella",                73,      40},

        {"waterproof trousers",     42,      70},

        {"waterproof overclothes",  43,      75},

        {"note-case",               22,      80},

        {"sunglasses",              7,       20},

        {"towel",                   18,      12},

        {"socks",                   4,       50},

        {"book",                    30,      10}

```
};
```
```
 
```

#define n_items (sizeof(item)/sizeof(item_t))

```
 
```
```
typedef struct {
```

        uint32_t bits; /* 32 bits, can solve up to 32 items */

```
        int value;
```
```
} solution;
```
```
 
```

void optimal(int weight, int idx, solution *s)

```
{
```
```
        solution v1, v2;
```
```
        if (idx < 0) {
```
```
                s->bits = s->value = 0;
```
```
                return;
```
```
        }
```
```
 
```

        if (weight < item[idx].weight) {

                optimal(weight, idx - 1, s);

```
                return;
```
```
         }
```
```
 
```
```
        optimal(weight, idx - 1, &v1);
```

        optimal(weight - item[idx].weight, idx - 1, &v2);

```
 
```
```
        v2.value += item[idx].value;
```
```
        v2.bits |= (1 << idx);
```
```
 
```

        *s = (v1.value >= v2.value) ? v1 : v2;

```
}
```
```
 
```
```
int main(void)
```
```
{
```
```
        int i = 0, w = 0;
```
```
        solution s = {0, 0};
```
```
        optimal(400, n_items - 1, &s);
```
```
 
```
```
        for (i = 0; i < n_items; i++) {
```

                if (s.bits & (1 << i)) {

                        printf("%s\n", item[i].name);

                        w += item[i].weight;

```
                }
```
```
        }
```

        printf("Total value: %d; weight: %d\n", s.value, w);

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

$ gcc knapsack.c -o knapsack
$ ./knapsack
 
map
compass
water
sandwich
glucose
banana
suntancream
waterproof trousers
waterproof overclothes
note-case
sunglasses
socks
Total value: 1030; weight: 396

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Booth’s Multiplication Algorithm for Multiplication

» Next - C Program to Solve the Fractional Knapsack Problem

Related Posts:

Recommended Articles: