Search⌘ K
AI Features
Home
Courses
Competitive Programming - Crack Your Coding Interview, C++

Greedy Knapsack Problem - Implementation

Understand how to implement the Greedy Knapsack algorithm in C++ by sorting items based on their value-to-weight ratio. Learn how to add whole or fractional items to maximize profit while respecting knapsack capacity.

We'll cover the following...

Implementation

We have already discussed the logic in Greedy Knapsack Problem lesson. Let’s directly jump to the code now.

C++
#include <bits/stdc++.h>
using namespace std;
struct Item {
	int value, weight;
	Item(int value, int weight)
	{
    	this->value=value;
	    this->weight=weight;
	}
};
bool cmp(struct Item a, struct Item b)
{
	double r1 = (double)a.value / (double)a.weight;
	double r2 = (double)b.value / (double)b.weight;
	return r1 > r2;
}
double fractionalKnapsack(int W, struct Item arr[], int n)
{
	sort(arr, arr + n, cmp);
	int curWeight = 0; // Current weight in knapsack
	double finalvalue = 0.0; // Result (value in Knapsack)
	for (int i = 0; i < n; i++) {
		if (curWeight + arr[i].weight <= W) {
			curWeight += arr[i].weight;
			finalvalue += arr[i].value;
		}
		else {
			int remain = W - curWeight;
			finalvalue += arr[i].value * ((double)remain / (double)arr[i].weight);
			break;
		}
	}
	return finalvalue;
}
int main()
{
	int W = 50; 
	Item arr[] = { { 60, 10 }, { 100, 20 }, { 120, 30 } };
	int n = sizeof(arr) / sizeof(arr[0]);
	cout << "Maximum Profit we can obtain = " << fractionalKnapsack(W, arr, n);
	return 0;
}

Explanation:

  • On line 4, we define a structure Item for an item that stores weight and its corresponding value (profit).
  • On line 7, we create a constructor for our structure Item, which will assign the profit and the weight of an Item.
  • In this code, we are going to use the built-in sort() function to sort the items based on the valueweight\frac{value}{weight}
...