In 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 n piles 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 hold W kilograms.
Given n, v, c and W, 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(n2) 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.
2007-11-20 at 18:04
[…] more here Der Beitrag wurde am Tuesday, den 20. November 2007 um 07:35 Uhr veröffentlicht und wurde […]
2008-08-05 at 10:42
its good program, but it will be best if we can input the elemnts arry at first of program, so can you modify the program so we can input the array as we wish!
2008-09-27 at 16:03
nice program easy to understand
2011-10-04 at 10:26
thank u baby……
2008-10-13 at 16:25
nice program
2008-10-21 at 0:44
You’re output doesn’t match the program. When I compiled and ran it, it gave the total value as 17.33.
2008-11-10 at 7:39
really it is simple to understand.thank u very much if you have 0-1 knapsack ,and other type knapsack problems solutions plz mail to /post here me .also suggest me any lecturre notes or site to learn ” design & analysis of algorithims ” which is in my curriculum
2008-12-16 at 21:21
is investment algoritm are same to Fractional Knapsack Problem?????
how i can ran investment thru Knapsack algoritm
link to investment algoritm :
http://www.scuec.edu.cn/jsj/scuec_cs/jinping/algorithm/res/ppt/Lecture12.ppt
plese ansqer me to mail insurgentx@walla.com
2008-12-22 at 20:10
nice work!!
2009-02-07 at 7:04
biasa ae..
aku malah iso’ sing the biner knapsack problem.
2009-04-29 at 6:38
gud work
2009-05-01 at 23:21
can you plz tell me what is the difference between fractional knapsack and 0-1 knapsack problem ? hope you will answer !
2015-11-24 at 9:32
• Both fractional and integral knapsack have optimal substructure.
• Only fractional knapsack has the greedy choice property
2018-04-14 at 13:47
Can I get opengl code for knapsack problem plz
It’s urgent it will be very helpful
2009-05-27 at 21:45
@rajat: In the 0-1 problem you can think about that the products used to fill the thief’s bag are solid like a gold ingot — or you put the whole item inside the bag or nothing. In fractional one you can think about something like dust, what I mean is, the thief can take some part of each one of the items available to steal.
2009-10-27 at 6:12
good job…..
2009-11-21 at 5:44
program use for real world
2009-12-05 at 17:47
what is the application of fractional knapsack problem in actual practice of computer application
2009-12-13 at 10:46
Hey ,this is very useful article for those who are really searching about the Fractional knapsack problem ,given program also helps us.
thanks…..
2010-04-20 at 12:54
Great job!
2010-04-22 at 18:11
#include
#include
main()
{
int n,j,i,a[10],t;
int w[10],v[10],W,temp,amount,p[10],sol[10];
clrscr();
printf(“\t\tFRACTIONAL KNAPSACK PROBLEM\n\n\n”);
printf(“ENTER NO. OF ITEMS\t:”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
a[i]=i;
printf("\nENTER WEIGHT OF ITEM A%d\t:",i);
scanf("%d",&w[i]);
printf("\nENTER VALUE OF ITEM A%d\t:",i);
scanf("%d",&v[i]);
}
printf("\n\nENTER MAXIMUM CAPACITY OF KNAPSACK\t:");
scanf("%d",&W);
for(i=0;i<n;i++)
p[i]=v[i]/w[i];
for(i=0;i<n;i++)
for(j=0;j<n-1;j++)
{
if(p[j]<=p[j+1])
{
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
temp=w[j];
w[j]=w[j+1];
w[j+1]=temp;
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
i=0;
amount=0;
while(W!=0)
{
if(W<w[i])
amount=W;
else
amount=w[i];
W=W-amount;
sol[i]=amount;
i++;
}
printf("FINAL SOLUTION IS\t:");
for(j=0;j<i;j++)
printf("A%d\t%d\n",a[j],sol[j]);
getch();
}
2012-10-28 at 17:51
Thnks.,
2010-04-22 at 18:12
the coding for fractional knapsack problem is given above…
2010-11-26 at 17:08
thanks
ur program is better then the given one.
2010-11-27 at 14:05
Ur welcome :)
2011-09-17 at 12:38
tanks brother……
2012-05-29 at 9:55
far better than the above solution!! thanx bro i was searchin for it
2010-06-23 at 7:06
Wait for only 2 days i will add my codind for fractional problem which is most efficint in complexity and high readibility
2010-07-07 at 10:04
this is a good program solution to solving the knapsack problem bt would be better by the use of an array as arparjit puts the problem.
Nice job,well done.
thanks
2010-11-27 at 14:08
ur welcome.. :)
2010-10-19 at 21:52
thanks for your effort
2010-10-25 at 9:57
is there any difference b/w fractional knapsack problem and 0-1 knapsack problem?
2010-10-28 at 8:41
Thx for source code,…
2011-01-18 at 18:53
please prove the optimality of your algo
send the answer to my mail please
2011-03-13 at 15:36
isn’t it after the adding object 1 of 58% should be $17.33 ?
58% of $4 is 2.32
2011-07-17 at 16:53
Total Value in bag:= $17.33
Item_no value weight value/weight
1) 4 12 0.33
2) 2 1 2
3) 2 2 1
4) 1 1 1
5) 10 4 2.5
Now rearrange in non decreasing order of value/weight, we have
Item_no value weight value/weigh
1) 10 4 2.5
2) 2 1 2
3) 2 2 1
4) 1 1 1
5) 4 12 0.33
Now we select the items :
—Select item 1, value=10, weight now avaiable: 15-4:= 11
—Select item 2, total value=10 + 2(value of item 2):= 12, weight now available: 11-1:10
—Select item 3, total value=12 +2=14, weight now available: 10-2=8
—Select item 4, total value=14+1=15, weight now available: 8-1=7
—Now we can’t select item 5 completely, so we’ll have to select it partially i.e. 7/12. total value=15 + ((4/12)*7))=15+2.33= 17.33
2013-09-22 at 18:34
Thanks man. Your answer was very helpful for the prepartion of my exam.
Can you just explain me about the job sequencing with deadlines from algorithm.
2011-09-17 at 12:36
hi…frds….i want some notes about “implementation of knapsack using backtracking”…………please :):)
2012-04-10 at 10:06
what the hell max is declared to be -1 in starting thgan yoy have used that index to refer two arrays now you mister programming fuckjing master why you did that.whyyyyyyyyyyyyyyyyyyy
2012-10-03 at 10:42
sir i cant understand plz say some more good
2012-11-29 at 11:00
# include
# include
void knapsack(int n, float weight[], float profit[], float capacity);
float mainweight[20];
int main() //manwar_ice@yahoo.com
{
float weight[20], profit[20], capacity;
int n, i ,j;
float ratio[20], temp;
//clrscr();
printf (“\n Enter the no. of objects: “);
scanf (“%d”, &n);
printf (“\n Enter the Weights and Profits of each object: “);
for (i=0; i<n; i++)
{
scanf("%f %f", &weight[i], &profit[i]);
}
printf ("\nEnter the capacity of knapsack: ");
scanf ("%f", &capacity);
for (i=0; i<n; i++)
{
mainweight[i]=weight[i];
}
for (i=0; i<n; i++)
{
ratio[i]=profit[i]/weight[i];
}
for(i=0; i<n; i++)
{
for(j=i+1;j< n; j++)
{
if(ratio[i]<ratio[j])
{
temp= ratio[j];
ratio[j]= ratio[i];
ratio[i]= temp;
temp= weight[j];
weight[j]= weight[i];
weight[i]= temp;
temp= profit[j];
profit[j]= profit[i];
profit[i]= temp;
}
}
}
knapsack(n, weight, profit, capacity);
getch();
}
void knapsack(int n, float weight[], float profit[], float capacity)
{
float x[20], tp= 0;
int i, j, u;
u=capacity;
for (i=0;i<n;i++)
x[i]=0.0;
for (i=0;iu)
break;
else
{
x[i]=1.0;
tp= tp+profit[i];
u=u-weight[i];
}
}
if(i<n)
x[i]=u/weight[i];
tp= tp + (x[i]*profit[i]);
printf("\n The result vector is: \n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if (mainweight[i]==weight[j])
{
printf("%.2f\t",x[j]);
break;
}
}
printf("\n\nMaximum profit is: %f", tp);
}
2013-02-19 at 15:53
Can anyone post opengl code for fractional knapsack problem ???…it would br very helpful….thank you.
2014-05-23 at 4:32
Does your blog have a contact page? I’m having problems locating it but, I’d like to send you an email.
I’ve got some creative ideas for your blog you might
be interested in hearing. Either way, great blog and I look forward to seeing it grow over time.
2014-06-25 at 2:03
Hey! I’m at work surfing around your blog from my new iphone 3gs!
Just wanted to say I love reading your blog and look
forward to all your posts! Keep up the fantastic work!
2014-08-01 at 5:06
I think it is one of the a whole lot information for me. And i’m happy studying ones report. Nonetheless need to thoughts for some elementary issues, The web site type is usually great, a posts is at fact wonderful : Chemical. Good procedure, all the best
2014-08-29 at 3:22
Hello to all, how is the whole thing, I think
every one is getting more from this site, and your views are good in support of new viewers.
2014-11-11 at 19:00
THANX
SO MUCH
2014-11-12 at 3:39
urban rivals machine a sous iphone
The Fractional Knapsack Problem | Computer programming
2018-04-14 at 13:44
Can I get opengl code for knapsack problem plz
2018-12-10 at 10:56
Online Games
The Fractional Knapsack Problem | Computer programming
2019-10-20 at 6:43
For most recent information you have to visit the web and on world-wide-web I found this web site as a finest web site for newest updates.|
2020-10-23 at 18:28
johnna
The Fractional Knapsack Problem | Computer programming