2007-11-20

## The Fractional Knapsack Problem

Posted by scvalexIn this article, I describe the greedy algorithm for solving the Fractional Knapsack Problem and give an implementation in C.

#### The Problem

The Fractional Knapsack Problem usually sounds like this:

Ted Thief has just broken into the Fort Knox! He sees himself in a room with

npiles of gold dust. Because the each pile has a different purity, each pile also has a different value (v[i]) and a different weight (c[i]). Ted has a knapsack that can only holdWkilograms.Given

n,v,candW, calculate which piles Ted should completely put into his knapsack and which he should put only a fraction of.

So, for this input:

`n = 5`

c = {12, 1, 2, 1, 4}

v = {4, 2, 2, 1, 10}

W = 15

Ted should take piles *2*, *3*, *4* and *5* completely and about *58%* of pile *1*.

You’re usually dealling with a knapsack problem when you’re give the cost and the benefits of certain objects and asked to obtain the maximum benefit so that the sum of the costs is smaller than a given value. You’ve got the **fractional** knapsack problem when you can take fractions (as opposed to all or nothing) of the objects.

#### The Algorithm

This is a standard greedy algorithm. In fact, it’s one of the classic examples.

The idea is to calculate for each object the ratio of *value/cost*, and sort them according to this ratio. Then you take the objects with the highest ratios and add them until you can’t add the next object as whole. Finally add as much as you can of the next object.

So, for our example:

`v = {4, 2, 2, 1, 10}`

c = {12, 1, 2, 1, 4}

r = {1/3, 2, 1, 1, 5/2}

From this it’s obvious that you should add the objects: 5, 2, 3, 4 and then as much as possible of 1.

The output of my programme is this:

`Added object 5 (10$, 4Kg) completly in the bag. Space left: 11.`

Added object 2 (2$, 1Kg) completly in the bag. Space left: 10.

Added object 3 (2$, 2Kg) completly in the bag. Space left: 8.

Added object 4 (1$, 1Kg) completly in the bag. Space left: 7.

Added 58% (4$, 12Kg) of object 1 in the bag.

Filled the bag with objects worth 15.48$.

#### The Programme

Now, you could implement the algorithm as stated, but for practical reasons you may wish to trade speed for simplicity. That’s what I’ve done here: instead of sorting the objects, I simply go through them every time searching for the best ratio. This modification turns an **O(n*lg(n))** algorithm into an **O(n ^{2})** one. For small values of

**n**, this doesn’t matter and

**n**is usually small.

Here’s the code in C (fractional_knapsack.c):

#include <stdio.h> int n = 5; /* The number of objects */ int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what YOU PAY to take the object */ int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e. what YOU GET for taking the object */ int W = 15; /* The maximum weight you can take */ void simple_fill() { int cur_w; float tot_v; int i, maxi; int used[10]; for (i = 0; i < n; ++i) used[i] = 0; /* I have not used the ith object yet */ cur_w = W; while (cur_w > 0) { /* while there's still room*/ /* Find the best object */ maxi = -1; for (i = 0; i < n; ++i) if ((used[i] == 0) && ((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi]))) maxi = i; used[maxi] = 1; /* mark the maxi-th object as used */ cur_w -= c[maxi]; /* with the object in the bag, I can carry less */ tot_v += v[maxi]; if (cur_w >= 0) printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w); else { printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1); tot_v -= v[maxi]; tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi]; } } printf("Filled the bag with objects worth %.2f$.\n", tot_v); } int main(int argc, char *argv[]) { simple_fill(); return 0; }

That’s it. Good luck.

Always open to comments.

Update: The next article in this series is The 0-1 Knapsack Problem.