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;

`}`

advertisement

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

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

advertisement

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