×

String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding

Miscellaneous

Fractional knapsack problem

In this article, we are discussing practical implementation of fractional knapsack problem. It can be solve using the greedy approach. Submitted by Vivek Kothari, on December 02, 2018

Prerequisites: Algorithm for fractional knapsack problem

Here, we are discussing the practical implementation of the fractional knapsack problem. It can be solved using the greedy approach and in fractional knapsack problem, we can break items i.e we can take a fraction of an item. For examples, you can read this article first.

Problem statement: We have given items i1, i2, ..., in (item we want to put in our bag) with associated weights w1, w2, ..., wn and profit values P1 , P2 ,..., Pn. Now problem is how we can maximize the total benefit given capacity of bag is C?

Algorithm

  1. Compute the profit per weight density for each item using the formula di = Pi / wi.
  2. Sort each item by its profit per weight density.
  3. Maximize the profit i.e Take as much as possible of the profit per weight density item not already in the bag.

C++ implementation of fractional knapsack problem

#include <bits/stdc++.h> 

using namespace std; 

// Structure for an item
struct myItem 
{
	int itemNo; 
	int profit;
	int weight;
	float ppw; // profit per weight
}; 

// Comparison function to sort Item according to profit per weight ratio
bool cmp(struct myItem a, struct myItem b) 
{ 
	return a.ppw > b.ppw; 
} 

float fractionalKnapsack(int Capacity, struct myItem arr[], int n) 
{ 
	//calculating profit per weight ratio
	for(int i=0;i<n;i++)
	{
		arr[i].ppw = ((float)arr[i].profit / arr[i].weight);
	}

	// sorting Item on basis of profit per weight ratio 
	sort(arr, arr + n, cmp); 

	cout<<"details of all items : \n";
	cout<<"itemNo\t"<<"Profit\t"<<"Weight\t"<<"PPW\t"<<endl;
	for (int i = 0; i < n; i++) 
	{ 
		cout <<arr[i].itemNo<<"\t"<<arr[i].profit<<"\t"<<arr[i].weight<<"\t"<<((float)arr[i].ppw)<<endl; 
	}

	cout<<endl;

	float Max = 0.0; // Maximum profit
	int i=0; 

	//take items until capacity becomes zero
	while(Capacity > 0 && i<=n-1)
	{
		// if we can take all weights of item
		if(Capacity >= arr[i].weight)
		{
			Max = Max + (float)arr[i].profit;
			Capacity = Capacity - arr[i].weight;
		}
		// we can take only fraction of item
		else
		{
			Max += (Capacity * arr[i].ppw);
			Capacity = 0;
		}
		i++;
	}  

	return Max; 
} 

// driver function
int main() 
{ 
	int C = 25;   //    Capacity of knapsack 
	myItem arr[] = { {1, 30, 10, 0}, {2, 20, 5, 0} , {3, 40, 15, 0}, {4, 36, 8, 0}}; 

	int n = sizeof(arr) / sizeof(arr[0]);

	cout<<"details of all items before sorting and without calculating PPW: \n";
	cout<<"itemNo\t"<<"Profit\t"<<"Weight\t"<<"PPW\t"<<endl;
	for (int i = 0; i < n; i++) 
	{ 
		cout <<arr[i].itemNo<<"\t"<<arr[i].profit<<"\t"<<arr[i].weight<<"\t"<<((float)arr[i].ppw)<<endl; 
	} 

	cout<<endl;
	cout << "Maximum profit we can obtain = "<< fractionalKnapsack(C, arr, n);

	return 0; 
} 

Output

details of all items before sorting and without calculating PPW:
itemNo  Profit  Weight  PPW
1       30      10      0
2       20      5       0
3       40      15      0
4       36      8       0

details of all items :
itemNo  Profit  Weight  PPW
4       36      8       4.5
2       20      5       4
1       30      10      3
3       40      15      2.66667

Maximum profit we can obtain = 91.3333


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.