Competitive Programming - Crack Your Coding Interview, C++/

...

/

Greedy Knapsack Problem - Implementation

Greedy Knapsack Problem - Implementation

Learn how to implement the solution for the Greedy Knapsack Problem.

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}
...