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,

Read number of items to variable n
Read capacity of knapsack to variable m
Initialize remaining capacity of the knapsack as u=m (initially remaining capacity is full capacity)
Initialize solution array x[] with value 0 in indices 0 to n-1
Read the weights and profits of each item into two separate arrays w[] and p[]
Find the Pi/Wi ratio of each item and store in array ratio[]
Sort the ratio[] array in its descending order. Rearrange the corresponding values in other arrays p[] and w[] along with it.
Display the sorted table (Print the arrays p[] ,w[] and ratio[])
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
Display the solution array x[]
Calculate total profit and total weight by simply multiplying and accumulating x[i]*p[i] and x[i]*w[i]
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.

Web Design for Beginners in Malayalam - Full Course (മലയാളം)
WATCH VIDEO

Open in OnlineGDB

//C Program to Simulate KnapSack Problem
// Code by Nived Kannada 
#include<stdio.h>

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

  //Reading number of items
  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;
  }

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

  //Reading the Profit values
  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 
//Code by Nived Kannada 
// 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!

This article and the code were written by Nived Kannada. Follow on Instagram to show your support.

Thanks.