Summary: In this tutorial, we will learn what Fractional Knapsack Problem is and how to solve fractional knapsack problem using Greedy algorithm in C++ and Java.
What is the Greedy Algorithm?
Consider you want to buy a car – one having the best features whatever the cost may be.
What will you do?
If you start looking and comparing each car in the world. It will take a lot of time.
The best way is to shortlist the best car’s brand and filter out all the infamous ones that do not produce good quality cars.
Next, you would filter the cars based on their performance.
By doing this, your task becomes easier i.e. the chances of getting your desired car have increased.
This approach of solving our problem is known as Greedy approach.
In the greedy approach, we sort or filter data in such a way that we don’t have to compare or analyze every data to solve our problem. We just care for those data which are relevant and useful to us.
Introduction to Fractional Knapsack Problem
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
Wikipedia
For example, suppose you are given 10 types of vegetables which weigh different and the total weight of 10 vegetables is around 25 kg. You have a bag that can hold a maximum of 10 kg of vegetables.
Here 10 kg limit is also known as Knapsack bag or Knapsack weight.
How will you choose the vegetables for your bag?
Definitely, you will choose vegetables that are fresh or has more nutrient value.
But there can be a problem.
The vegetables which have high nutrient value can weigh more than low nutritional vegetables, due to which you will have to carry fewer vegetables in your 10 kg capacity bag.
What to do now?
Since you want vegetables with high nutrient value and less weight, so that you can accommodate more vegetables in your bag, you are likely to follow this rule.
vegetable ~ nutrient-value
vegetable ~ 1/weight
which combines to
vegetable ~ nutrient-value / weight
Thus, the best way is to use a greedy approach i.e. sort the vegetables in order of decreasing nutrient-value / weight ratio (which you can call density) and take the vegetables with higher ratio value until the bag is full.
In this way, you don’t have to compare vegetables because you have already sorted them based on the nutrient-value/weight ratio. You don’t even have to look at those vegetables which are at the lower end of the nutrient-value/weight value (except if your bag is not full).
The most important point is that we can take the fraction of the last item to completely fill our bag (if adding a whole item exceeds W). That’s why its called a fractional knapsack problem.
Fractional Knapsack Problem Solution in C++ and Java
The same approach we are using in our program.
- We have taken an array of structures named
Item. - Each
Itemhasvalue&weight. - We are calculating
density= value/weightfor each item and sorting the items array in the order of decreasing density. - We add values from the top of the array to
totalValueuntil the bag is full i.e.totalValue<=W( where W is Knapsack weight).
Here is the implementation of the above knapsack problem in C++ and Java.
C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef struct {
int value;
int weight;
float density;
}Item;
void input(Item items[],int sizeOfItems){
cout << "Enter total "<< sizeOfItems <<" item's values and weight" << endl;
for(int i=0; i<sizeOfItems; i++){
cout << "Enter "<< i+1 << " Value ";
cin >> items[i].value;
cout << "Enter "<< i+1 << " Weight ";
cin >> items[i].weight;
}
}
void display(Item items[],int sizeOfItems){
cout << "values: ";
for(int i=0; i<sizeOfItems; i++){
cout << items[i].value << "\t";
}
cout << endl << "weight: ";
for(int i=0; i<sizeOfItems; i++){
cout << items[i].weight << "\t";
}
cout << endl;
}
bool compare(Item i1, Item i2){
return (i1.density > i2.density);
}
float knapsack(Item items[],int sizeOfItems, int W){
float totalValue=0, totalWeight=0;
//calculating density of each item
for(int i=0; i<sizeOfItems; i++){
items[i].density = items[i].value/items[i].weight;
}
//sorting w.r.t to density using compare function
sort(items, items+sizeOfItems,compare);
for(int i=0; i<sizeOfItems; i++){
if(totalWeight + items[i].weight<= W){
totalValue += items[i].value ;
totalWeight += items[i].weight;
} else {
int wt = W-totalWeight;
totalValue += (wt * items[i].density);
totalWeight += wt;
break;
}
}
cout << "total weight in bag " << totalWeight<<endl;
return totalValue;
}
int main()
{
int W;
Item items[3];
input(items,3);
cout << "Entered data \n";
display(items,3);
cout<< "Enter Knapsack weight \n";
cin >> W;
float mxVal = knapsack(items,3,W);
cout << "---Max value for "<< W <<" weight is "<< mxVal;
return 0;
}Java
import java.util.Scanner;
public class Item {
int value;
int weight;
float density;
public Item(int value, int weight, float density) {
this.value = value;
this.weight = weight;
this.density = density;
}
}
public class Knapsack {
Item[] items;
int W;
public Knapsack(Item[] items, int W) {
this.items = items;
this.W = W;
}
public float solve(){
int i, j, pos;
Item mx,temp;
float totalValue=0, totalWeight=0;
//calculating density of each item
for(i=0; i<items.length; i++){
items[i].density = (float) items[i].value/items[i].weight;
}
//sorting w.r.t to density by using compare function
for(i=0; i<items.length; i++){
mx = items[i];
pos= i;
for(j=i; j<items.length; j++){
if(items[j].density> mx.density){
mx= items[j];
pos = j;
}
}
temp = items[i];
items[i] = mx;
items[pos] = temp;
}
for(i=0; i<items.length; i++){
if(totalWeight + items[i].weight<= W){
totalValue += items[i].value ;
totalWeight += items[i].weight;
} else {
int wt = (int) (W-totalWeight);
totalValue += (wt * items[i].density);
totalWeight += wt;
break;
}
}
System.out.println("total weight in bag "+totalWeight);
return totalValue;
}
}
public class App {
static Scanner in = new Scanner(System.in);
public static void main(String args[]){
int n=3, W;
Item[] items = new Item[3];
System.out.println("Enter data");
System.out.println("Enter total "+n+" item's values and weight");
for(int i=0; i<n; i++){
Item item = new Item(0,0,0);
System.out.print("Enter "+(i+1)+" Value ");
item.value = in.nextInt();
System.out.print("Enter "+(i+1)+" Weight ");
item.weight = in.nextInt();
items[i] = item;
}
System.out.println("Entered data");
display(items);
System.out.println("Enter Knapsack Weight");
W = in.nextInt();
Knapsack ks = new Knapsack(items, W);
float mxVal = ks.solve();
System.out.println("---Max value for "+ W +" weight is "+mxVal);
}
static void display(Item items[]){
System.out.print("values: ");
for(int i=0; i<items.length; i++){
System.out.print(items[i].value + "\t");
}
System.out.println();
System.out.print("weight: ");
for(int i=0; i<items.length; i++){
System.out.print(items[i].weight+"\t");
}
System.out.println();
}
}Output:
In this tutorial, we learned what the greedy algorithm and the fractional knapsack problem are. We also learned how to solve the Fractional Knapsack problem using the Greedy algorithm in C++ and Java.