The Knapsack Problem is also called as rucksack problem. A basic c program is written to solve knapsack problem given with set of items each with a mass and value. Describe every individual item included in a collection so that total weight is less than or equal to a given limit and total value is as large as possible. A fixed size knapsack is defined at the beginning. It must fill with most valuable items.
Here is the source code in c program used to solve knapsack problem. It is successfully compiled and tested on Linux system. The output is shown below.
Source code:
#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;
}
Output:
$ gcc knapsack.c -o knapsack
$ ./knapsack
Value = 220