Program to solve the knapsack problem in C++

In this tutorial, we will learn how to solve the knapsack problem using a C++ program. We can use it for good decision-making to solve real-world problems. Here we will use it to find the maximum profit that can be gained with a set of items. If you are looking for a C++ program to find the solution to the knapsack problem you are in the right place.

Solving the knapsack problem

In the problem, there is a sack having a specific capacity and a set of items or products with their weights. So, using this information, we have to find the items so that we get the maximum profit from the products. So, to solve a given knapsack problem follow the steps given below –

  • Calculate the profit-weight ratio for each item or product.
  • Arrange the items on the basis of ratio in descending order.
  • Take the product having the highest ratio and put it in the sack.
  • Reduce the sack capacity by the weight of that product.
  • Add the profit value of that product to the total profit.
  • Repeat the above three steps till the capacity of sack becomes 0 i.e. until the sack is full.

C++ program to solve the knapsack problem

We will use the structure data structure to implement the same. Firstly, we have to take the number of items or products and the capacity of the sack. Then, we have to take the profit and weight of each item from the user and calculate the profit-weight ratio. To find the maximum profit, we have to select the items with a high profit-weight ratio and put them in the sack. We get the maximum profit for the given knapsack problem when the sack is full. Let us see the C++ program to solve the same.

#include<iostream>
#define MAX 10
using namespace std;
struct product
{
  int product_num;
  int profit;
  int weight;
  float ratio;
  float take_quantity;
};
int main()
{
  product P[MAX],temp;
  int i,j,total_product,capacity;
  float value=0;
  cout<<"ENTER NUMBER OF ITEMS : ";
  cin>>total_product;
  cout<<"ENTER CAPACITY OF SACK : ";
  cin>>capacity;
  cout<<"\n";
  for(i=0;i<total_product;++i)
  {
    P[i].product_num=i+1;
    cout<<"ENTER PROFIT AND WEIGHT OF PRODUCT "<<i+1<<" : ";
    cin>>P[i].profit>>P[i].weight;

    P[i].ratio=(float)P[i].profit/P[i].weight;
    P[i].take_quantity=0;
  }

  //HIGHEST RATIO BASED SORTING
  for(i=0;i<total_product;++i)
  {
    for(j=i+1;j<total_product;++j)
    {
      if(P[i].ratio<P[j].ratio)
      {
        temp=P[i];
        P[i]=P[j];
        P[j]=temp;
      }
    }
  }
  for(i=0;i<total_product;++i)
  {
    if(capacity==0)
      break;
    else if(P[i].weight<capacity)
    {
      P[i].take_quantity=1;
      capacity-=P[i].weight;
    }
    else if(P[i].weight>capacity)
    {
      P[i].take_quantity=(float)capacity/P[i].weight;
      capacity=0;
    }
  }

  cout<<"\n\nPRODUCTS TO BE TAKEN -";
  for(i=0;i<total_product;++i)
  {
    cout<<"\nTAKE PRODUCT "<<P[i].product_num<<" : "<<P[i].take_quantity*P[i].weight<<" UNITS";
    value+=P[i].profit*P[i].take_quantity;
  }
  cout<<"\nTHE KNAPSACK VALUE IS : "<<value;
  return 0;
}

The structure array variable ‘P’ stores the details of all items or products. After taking the input from the user, we sort the array on the basis of the profit-weight ratio. Then, we add the items profit-wise, and the weight of the item subtracts the capacity of the sack. Finally, the program displays the knapsack value with the individual items with their weights.

C++ program output

Finally, the above program displays the items and their weights that are to be put in the sack. And the maximum profit for the given problem which is also called the knapsack value. So, the output of the above program is as follows –

[email protected]:~/cpp$ g++ knapsack.cpp
[email protected]:~/cpp$ ./a.out
ENTER NUMBER OF ITEMS : 7
ENTER CAPACITY OF SACK : 15

ENTER PROFIT AND WEIGHT OF PRODUCT 1 : 10 2
ENTER PROFIT AND WEIGHT OF PRODUCT 2 : 5 3
ENTER PROFIT AND WEIGHT OF PRODUCT 3 : 15 5
ENTER PROFIT AND WEIGHT OF PRODUCT 4 : 7 7
ENTER PROFIT AND WEIGHT OF PRODUCT 5 : 6 1
ENTER PROFIT AND WEIGHT OF PRODUCT 6 : 18 4
ENTER PROFIT AND WEIGHT OF PRODUCT 7 : 3 1


PRODUCTS TO BE TAKEN -
TAKE PRODUCT 5 : 1 UNITS
TAKE PRODUCT 1 : 2 UNITS
TAKE PRODUCT 6 : 4 UNITS
TAKE PRODUCT 3 : 5 UNITS
TAKE PRODUCT 7 : 1 UNITS
TAKE PRODUCT 2 : 2 UNITS
TAKE PRODUCT 4 : 0 UNITS
THE KNAPSACK VALUE IS : 55.3333
[email protected]:~/cpp$

The knapsack problem given in the output contains 7 items and the sack capacity is 15. The user enters 7 items and their respective weights. Then, the program finds the products to be taken and the knapsack value of the problem.

Also read: Calculate factorial of a number in C++

Leave a Reply

Your email address will not be published. Required fields are marked *