Implementing Knapsack Problem in C Programming

Tweet

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight 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.

In this post, I will demonstrate how to implement it using C programming language.

#include<stdio.h>
void swap(float *a,int x,int y)
{
 int temp=*(a+x);
 *(a+x)=*(a+y);
 *(a+y)=temp;
}
void swap1(int *a,int x,int y)
{
 int temp=*(a+x);
 *(a+x)=*(a+y);
 *(a+y)=temp;
}
main()
{
 printf("\nProgram to implement Knapsack problem : \n");
 int n,i,j,kn,kn2;  
 printf("\nEnter knapsack capacity : ");
 scanf("%d",&kn);
 kn2=kn;
 printf("\nEnter no. of elements : ");
 scanf("%d",&n);
 int index[n];
 float weight[n],profit[n],prowt[n],totwt=0,rem=0,rem2=0,rem3=0; 
 for(i=0;i<n;i++)
  index[i]=i;
 printf("\nEnter weight and profit for each element : \n");
 printf("\n\t\tWeight\tProfit\n");
 for(i=0;i<n;i++)
 {
  printf("Element %d : \t",index[i]);
  scanf("%f%f",&weight[i],&profit[i]);
  prowt[i]=profit[i]/weight[i];   
 }
 for(i=0;i<n;i++)
  for(j=0;j<n-1-i;j++)
   if(prowt[j]<prowt[j+1])
   {
    swap1(index,j,j+1);
    swap(prowt,j,j+1);
    swap(weight,j,j+1);
    swap(profit,j,j+1);
   }
 printf("\nDetails entered by user (after sorting): \n");
 printf("\n\t\tWeight\t\tProfit\t\tProfit per wt.\n");
 for(i=0;i<n;i++)
 {
  printf("Element %d : ",index[i]);
  printf("\t%5.4f\t\t%5.4f\t\t%5.4f\n",weight[i],profit[i],prowt[i]);
 }
 for(i=0;i<n;i++)
 {
  if(totwt + weight[i] < kn)
  {
   totwt=totwt+weight[i];
   kn2=kn2-weight[i];
   printf("\n\nElement %d inserted completely in the knapsack ...",index[i]);
   printf("\nTotal weight of Knapsack : %4.2f",totwt);
   printf("\nRemaining capacity : %d",kn2);
  }
  else
  {
   rem=weight[i]-kn2;
   rem2=rem/weight[i];    
   rem3=(float)(1-rem2)*100;
   totwt=totwt+kn2;
   printf("\n\nOnly %4.2f %% of element %d inserted in the knapsack ...",rem3,i);
   printf("\nTotal weight of Knapsack : %4.2f",totwt);
   printf("\n\n\t***** Knapsack is full *****\n");
   break;
  }
 } 
}   

The output of the program will be like this :

Program to implement Knapsack problem :

Enter knapsack capacity : 10

Enter no. of elements : 3

Enter weight and profit for each element :

                      Weight    Profit
Element 0 :     6             10
Element 1 :     1              9
Element 2 :     5              5

Details entered by user (after sorting):

                        Weight        Profit        Profit per wt.
Element 1 :     1.0000        9.0000        9.0000
Element 0 :     6.0000        10.0000      1.0000
Element 2 :     5.0000        5.0000        1.0000


Element 1 inserted completely in the knapsack ...
Total weight of Knapsack : 1.00
Remaining capacity : 9

Element 0 inserted completely in the knapsack ...
Total weight of Knapsack : 7.00
Remaining capacity : 3

Only 60.00 % of element 2 inserted in the knapsack ...
Total weight of Knapsack : 10.00

    ***** Knapsack is full *****

Posted in: Programming in C