C Program to Solve the 0-1 Knapsack Problem

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.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdint.h>
  4.  
  5. typedef struct {
  6.         const char * name;
  7.         int weight, value;
  8. } item_t;
  9.  
  10. item_t item[] = {
  11.         {"map",                     9,       150},
  12.         {"compass",                 13,      35},
  13.         {"water",                   153,     200},
  14.         {"sandwich",                50,      160},
  15.         {"glucose",                 15,      60},
  16.         {"tin",                     68,      45},
  17.         {"banana",                  27,      60},
  18.         {"apple",                   39,      40},
  19.         {"cheese",                  23,      30},
  20.         {"beer",                    52,      10},
  21.         {"suntancream",             11,      70},
  22.         {"camera",                  32,      30},
  23.         {"T-shirt",                 24,      15},
  24.         {"trousers",                48,      10},
  25.         {"umbrella",                73,      40},
  26.         {"waterproof trousers",     42,      70},
  27.         {"waterproof overclothes",  43,      75},
  28.         {"note-case",               22,      80},
  29.         {"sunglasses",              7,       20},
  30.         {"towel",                   18,      12},
  31.         {"socks",                   4,       50},
  32.         {"book",                    30,      10}
  33. };
  34.  
  35. #define n_items (sizeof(item)/sizeof(item_t))
  36.  
  37. typedef struct {
  38.         uint32_t bits; /* 32 bits, can solve up to 32 items */
  39.         int value;
  40. } solution;
  41.  
  42. void optimal(int weight, int idx, solution *s)
  43. {
  44.         solution v1, v2;
  45.         if (idx < 0) {
  46.                 s->bits = s->value = 0;
  47.                 return;
  48.         }
  49.  
  50.         if (weight < item[idx].weight) {
  51.                 optimal(weight, idx - 1, s);
  52.                 return;
  53.          }
  54.  
  55.         optimal(weight, idx - 1, &v1);
  56.         optimal(weight - item[idx].weight, idx - 1, &v2);
  57.  
  58.         v2.value += item[idx].value;
  59.         v2.bits |= (1 << idx);
  60.  
  61.         *s = (v1.value >= v2.value) ? v1 : v2;
  62. }
  63.  
  64. int main(void)
  65. {
  66.         int i = 0, w = 0;
  67.         solution s = {0, 0};
  68.         optimal(400, n_items - 1, &s);
  69.  
  70.         for (i = 0; i < n_items; i++) {
  71.                 if (s.bits & (1 << i)) {
  72.                         printf("%s\n", item[i].name);
  73.                         w += item[i].weight;
  74.                 }
  75.         }
  76.         printf("Total value: %d; weight: %d\n", s.value, w);
  77.         return 0;
  78. }
$ 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.

advertisement
advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.