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 Reference Books in C Programming, Data Structures and Algorithms.