Fractional Knapsack Problem

YouTube Video: Part 2

In this tutorial we will learn about fractional knapsack problem, a greedy algorithm. In this problem the objective is to fill the knapsack with items to get maximum benefit (value or profit) without crossing the weight capacity of the knapsack. And we are also allowed to take an item in fractional part.

Points to remember

• In this problem we have a Knapsack that has a weight limit W
• There are items i1, i2, ..., in each having weight w1, w2, … wn and some benefit (value or profit) associated with it v1, v2, ..., vn
• Our objective is to maximise the benefit such that the total weight inside the knapsack is at most W
• And we are also allowed to take an item in fractional part

Problem

Assume that we have a knapsack with max weight capacity, W = 16.
our objective is to fill the knapsack with items such that the benefit (value or profit) is maximum.

Consider the following items and their associated weight and value

Steps

• Calculate value per weight for each item (we can call this value density)
• Sort the items as per the value density in descending order
• Take as much item as possible not already taken in the knapsack

Compute density = (value/weight)

Sort the items as per density in descending order

Now we will pick items such that our benefit is maximum and total weight of the selected items is at most W.

Knapsack table

Our objective is to fill the knapsack with items to get maximum benefit without crossing the weight limit W = 16.

How to fill the knapsack table?

is WEIGHT(i) + TOTAL WEIGHT <= W
if its YES
then we take the whole item

Values after calculation

So, total weight in the knapsack = 16 and total value inside it = 22.333336

Code

#include <stdio.h>

struct Item {
  char id[5];
  int weight;
  int value;
  float density;
};

void fractionalKnapsack(Item items[], int n, int W);

int main(void) {
  //variables
  int i, j;

  //list items
  Item items[6] = {
    {"i1",  6, 6, 0},
    {"i2", 10, 2, 0},
    {"i3",  3, 1, 0},
    {"i4",  5, 8, 0},
    {"i5",  1, 3, 0},
    {"i6",  3, 5, 0}
  };

  //temp item
  Item temp;

  //number of items
  int n = 6;

  //max weight limit of knapsack
  int W = 16;

  //compute desity = (value/weight)
  for(i = 0; i < n; i++) {
    items[i].density = float(items[i].value) / items[i].weight;
  }

  //sort by density in descending order
  for(i = 1; i < n; i++) {
    for(j = 0; j < n - i; j++) {
      if(items[j+1].density > items[j].density) {
        temp = items[j+1];
        items[j+1] = items[j];
        items[j] = temp;
      }
    }
  }

  fractionalKnapsack(items, n, W);

  return 0;
}

void fractionalKnapsack(Item items[], int n, int W) {
  int i, wt;
  float value;

  float totalWeight = 0, totalBenefit = 0;

  for(i = 0; i < n; i++) {
    if(items[i].weight + totalWeight <= W) {

      totalWeight += items[i].weight;
      totalBenefit += items[i].value;

      printf("Selected Item: %s\tWeight: %d\tValue: %d\tTotal Weight: %f\tTotal Benefit: %f\n", items[i].id, items[i].weight, items[i].value, totalWeight, totalBenefit);

    } else {
      wt = (W - totalWeight);
      value = wt * (float(items[i].value) / items[i].weight);

      totalWeight += wt;
      totalBenefit += value;

      printf("Selected Item: %s\tWeight: %d\tValue: %f\tTotal Weight: %f\tTotal Benefit: %f\n", items[i].id, wt, value, totalWeight, totalBenefit);

      break;
    }
  }

  printf("Total Weight: %f\n", totalWeight);
  printf("Total Benefit: %f\n", totalBenefit);
}

Output

Selected Item: i5  Weight: 1  Value: 3  Total Weight: 1.000000  Total Benefit: 3.000000
Selected Item: i6  Weight: 3  Value: 5  Total Weight: 4.000000  Total Benefit: 8.000000
Selected Item: i4  Weight: 5  Value: 8  Total Weight: 9.000000  Total Benefit: 16.000000
Selected Item: i1  Weight: 6  Value: 6  Total Weight: 15.000000  Total Benefit: 22.000000
Selected Item: i3  Weight: 1  Value: 0.333333  Total Weight: 16.000000  Total Benefit: 22.333334
Total Weight: 16.000000
Total Benefit: 22.333334