 Knapsack Problem C Program and explanation by Nived Kannada

The knapsack problem is a very interesting type of problem in computer science. It relates a usual computer science problem with the real-life application of filling a knapsack with items or objects in the most efficient way possible while solving the computer science counterpart of the same problem.

It might sound like a complex algorithm. But actually, it is very easy to learn and understand. So, in this article, we are going to see how to implement the Knapsack problem using C Programming along with its explanation. Literally, each part of the code is commented, so you can clearly get an idea of how it works.

The logic is very simple!

Imagine that you have a Knapsack of capacity m. If you have n objects in your hand and each object is associated with a profit value and a weight value, and you want to fill these objects into the knapsack in the most efficient/profitable way possible. This is basically what we call a knapsack problem.

The logic is as follow,

1. Read number of items to variable n
2. Read capacity of knapsack to variable m
3. Initialize remaining capacity of the knapsack as u=m (initially remaining capacity is full capacity)
4. Initialize solution array x[] with value 0 in indices 0 to n-1
5. Read the weights and profits of each item into two separate arrays w[] and p[]
6. Find the Pi/Wi ratio of each item and store in array ratio[]
7. Sort the ratio[] array in its descending order. Rearrange the corresponding values in other arrays p[] and w[] along with it.
8. Display the sorted table (Print the arrays p[] ,w[] and ratio[])
9. Calculate Solution array x[]
For each weight in w[] that is less than or equal to the value of u (ie. remaining capacity),
set x[i] = 1 and set reduce the value of u by the weight value w[i] (ie. u=u-w[i])
if w[i] becomes greater than u then simply break out of the loop and check whether i is less than or equal to n. If i<=n then simply calculate u/w[i] and store it in a variable xr
10. Display the solution array x[]
11. Calculate total profit and total weight by simply multiplying and accumulating x[i]*p[i] and x[i]*w[i]
12. Display the Total profit and Total weight
See, it's very simple and easy to understand. Now, let's see the actual code for all these steps.

```//C Program to Simulate KnapSack Problem
#include<stdio.h>

void main ()
{
int n, m, w, p, ratio , i, j, u, temp;
float xr, x, total_profit=0, total_weight=0;

printf ("Enter the number of items(n): ");
scanf ("%d", &n);

//Reading the capacity of the knapsack
printf ("Enter the capacity of the Knapsack(m): ");
scanf ("%d", &m);

//Initializing remaining capacity of Knapsack (u)
u = m;

//Initializing Solution Array x[]
for(i=0;i<n;i++)
{
x[i]=0;
}

printf ("Enter the Weights of items: ");
for (i = 0; i < n; i++)
{
printf ("\n\tWeight of item %d = ", i + 1);
scanf ("%d", &w[i]);
}

printf ("\nEnter the Profit Values of items: ");
for (i = 0; i < n; i++)
{
printf ("\n\tProfit of item %d = ", i + 1);
scanf ("%d", &p[i]);
}

//Calculating Pi/Wi ratio of each item and storing in array ratio[]
for (i = 0; i < n; i++)
{
ratio[i] = p[i] / w[i];
}

//Sorting all the arrays based on the ratio in descending order
for (i = 0; i < n; i++)
{
for (j = 0; j < n - 1; j++)
{
if (ratio[j] < ratio[i])
{
temp = ratio[i];
ratio[i] = ratio[j];
ratio[j] = temp;

temp = w[i];
w[i] = w[j];
w[j] = temp;

temp = p[i];
p[i] = p[j];
p[j] = temp;
}
}
}

//PRINTING THE SORTED TABLE
printf("\n The Table After Sorting based on the Ratio: \n");

//Printing Item numbers
printf("\nItem:\t\t");
for(i=0;i<n;i++)
{
printf("%d\t",i+1);
}

//Printing Profit Array
printf("\nProfit:\t\t");
for(i=0;i<n;i++)
{
printf("%d\t",p[i]);
}

//Printing Weight Array
printf("\nWeights:\t");
for(i=0;i<n;i++)
{
printf("%d\t",w[i]);
}

//Printing RATIO Array
printf ("\nRATIO:\t\t");
for (i = 0; i < n; i++)
{
printf ("%d\t", ratio[i]);
}

//Calculating Solution Array x
for(i=0;i<n;i++)
{
if(w[i]<=u)
{
x[i]=1;     //Setting solution index as 1
u=u-w[i];   //updating remaining knapsack capacity
}
else if(w[i]>u)
{
break;
}
}

if(i<=n)
{
xr = (float)u/w[i];    //Calculating what fraction of that item will fit into the knapsack
x[i] = xr;      //Setting this fraction to solution array
}

//Printing Solution Array x
printf("\n X = [");
for(i=0;i<n;i++)
{
printf("%.3f , ",x[i]);
}
printf("]");

//Calculating Total Profit & Total Weight
for(i=0;i<n;i++)
{
total_profit += x[i]*p[i];
total_weight += x[i]*w[i];
}

//Displaying Total Profit and Total Weight
printf("\nTotal Profit = %.2f \n Total Weight = %.2f ",total_profit,total_weight);

}

//End of Code
// www.nanogalaxy.org
```

## Sample Output

If you found this article helpful, please let us know in the comments below. If you found any errors in the code or the logic, please let us know. We are always happy to help. Thanks!