The 0-1 Knapsack Problem (AKA The Discrete Knapsack Problem) is a famous problem solvable by dynamic-programming. In this article, I describe the problem, the most common algorithm used to solve it and then provide a sample implementation in C.
If you’ve never heard of the Knapsack Problems before, it will help to read this previous post.
The Problem
The Discrete (0-1) Knapsack Problem usually sounds like this:
Little Red Riding Hood wants to bring grandma a basket of goodies. She has an unlimited supply of n types of sweets each weighting c[i] and having the nutritional value of v[i]. Her basket can hold at most W kilograms of sweets.
Given n, c, v and W, figure out which sweets and how many to take so that the nutritional value in maximal.
So, for this input:
n = 3
c = {8, 6, 4}
v = {16, 10, 7}
W = 10
LRRH should take one of 3 and one of 2, amassing 17 nutritional points.
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 have got the Discrete Knapsack Problem when you can only take the whole object or none at all and you have an unlimited supply of objects.
The Algorithm
This is a dynamic-programming algorithm.
The idea is to first calculate the maximum benefit for weight x and only after that to calculate the maximum benefit for x+1. So, on the whole, you first calculate the maximum benefit for 1, then for 2, then for 3, …, then for W-1 and, finally, for W. I store the maximum benefits in an array named a.
Start with a[0] = 0. Then for every a between 1 … W use the formula:a[i] = max{vj + a(i − cj) | cj ≤ i }
The basic idea is that to reach weight x, you have to add an object of weight w to a previous maximum benefit. More specifically, you have to add w to x – w. Now, there will probably be several ways to reach weight x, so you have to choose the one that maximises the benefit. That’s what the max is for.
Basically, the formula says: “To calculate the benefit of weight x, take every object (value: v; weight: w) and see if the benefit for x – w plus v is greater than the current benefit for x. If so, change it.”
So, for the example, the programme would output (and do) this:
Weight 0; Benefit: 0; Can't reach this exact weight.
Weight 1; Benefit: 0; Can't reach this exact weight.
Weight 2; Benefit: 0; Can't reach this exact weight.
Weight 3; Benefit: 0; Can't reach this exact weight.
Weight 4; Benefit: 7; To reach this weight I added object 3 (7$ 4Kg) to weight 0.
Weight 5; Benefit: 7; To reach this weight I added object 3 (7$ 4Kg) to weight 1.
Weight 6; Benefit: 10; To reach this weight I added object 2 (10$ 6Kg) to weight 0.
Weight 7; Benefit: 10; To reach this weight I added object 2 (10$ 6Kg) to weight 1.
Weight 8; Benefit: 16; To reach this weight I added object 1 (16$ 8Kg) to weight 0.
Weight 9; Benefit: 16; To reach this weight I added object 1 (16$ 8Kg) to weight 1.
Weight 10; Benefit: 17; To reach this weight I added object 2 (10$ 6Kg) to weight 4.
The Programme
This programme runs in pseudo-plynominal time O(n * W). i.e. Slow as hell for large very values of W. Also because it holds to arrays of at least length W, it’s also horribly memory inefficient. Unfortunately, there’s not much you can do.
Here’s the code in C (knapsack10.c):
#include <stdio.h>
#define MAXWEIGHT 100
int n = 3; /* The number of objects */
int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what
YOU PAY to take the object */
int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.
what YOU GET for taking the object */
int W = 10; /* The maximum weight you can take */
void fill_sack() {
int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained
using at most i weight */
int last_added[MAXWEIGHT]; /* I use this to calculate which object were
added */
int i, j;
int aux;
for (i = 0; i <= W; ++i) {
a[i] = 0;
last_added[i] = -1;
}
a[0] = 0;
for (i = 1; i <= W; ++i)
for (j = 0; j < n; ++j)
if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {
a[i] = a[i - c[j]] + v[j];
last_added[i] = j;
}
for (i = 0; i <= W; ++i)
if (last_added[i] != -1)
printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]);
else
printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);
printf("---\n");
aux = W;
while ((aux > 0) && (last_added[aux] != -1)) {
printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
aux -= c[last_added[aux]];
}
printf("Total value added: %d$\n", a[W]);
}
int main(int argc, char *argv[]) {
fill_sack();
return 0;
}
That’s it. Good luck. Always open to comments.
2007-11-20 at 21:11
[…] scvalex added an interesting post on The 0-1 Knapsack Problem […]
2007-11-21 at 7:56
[…] here for full story Der Beitrag wurde am Tuesday, den 20. November 2007 um 11:14 Uhr […]
2008-08-05 at 10:45
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-11-10 at 7:47
oh thank u
2008-11-10 at 20:20
The code is great
Thanx
2009-03-07 at 12:43
Yelo, can somebody modify the programe code that you can enter the cost and the value of parts and the maximum weight you can take??
It would be great, when it,s possible please send it by mail i would be very grateful:}
greeting Miro
2009-03-07 at 12:44
Here is my mail:) misq51@o2.pl
2009-03-18 at 4:25
is there bug in the program?
I tried to modify the value of c and v, into, let say:
c[]={3,4,5}
v[]={5,7,8}
w remain 10
from logic, we can say the max benefit is 15, but the program return 17…
2009-07-09 at 19:22
The max benefit is 17.
If you take 2 of 1, and 1 of 2.
Then you have weight
3, 3, 4 = 10, and value
5, 5, 7 = 17
2009-03-18 at 4:53
I guess I found out the reason.
during the if(c[j]<=1 …. ), you did not check if the item reuse.
maybe your problem is different from mine, your item can reuse, my problem cant reuse the item.
2009-03-20 at 19:19
how to check it?? that the item was reuse?
2009-03-20 at 19:54
For example, to reach weight 3, I added item 1; to reach weight 6, I added item 1 again… that’s the problem.
To prevent it from reuse, I added a table to record down, if the item was used for a particular weight, put as 1, else 0.
2009-03-21 at 13:02
can you write this part of the code? and the place were you must add it? thx
2009-03-24 at 14:24
Vhanded can you send me the modified program (c code) on my e-mail?? I would be very grateful :) it’s very important here is my mail: misq51@o2.pl
2009-03-31 at 10:40
//The code that I modified is here:
#include
#define MAXWEIGHT 100
int n = 5;
int c[]={2,4,3,5,7}; //cost aka weight
int v[]={3,7,9,8,4}; //value aka benefit
int W=15; //maximum weight can take(bag size)
int main()
{
int table[W][n];
for(int i=0; i<=W; i++)
{
for(int j=0; j<n; j++)
{
table[i][j]=0;
}
}
int a[W]; //this hold the maximum value that can can be obtained using at most i weight
for(int i=0; i<=W; i++)
{
a[i]=0;
}
for(int i=1; i<=W; ++i)
{
for(int j=0; j<n; ++j)
{
if((c[j]<=i)&&(a[i]<=(a[i-c[j]]+v[j]))&&table[i-c[j]][j]!=1)
//c[j]<=i, to allow only if selected weight bucket is less than i
//(a[i]<=(a[i-c[j]]+v[j]), to check if the previous weight bucket has closer value.
//table[i-c[j]][j]!=1 is to prevent the items reuse.
{
for(int k=0; k=a[i])
{
table[i][j]=1;
}
a[i]=newTotalBenefit;
}
}
}
printf(“\t”);
for(int i=0; i<n; i++)
{
printf(“%d “,i);
}
printf(“\n”);
for(int i=0; i<=W; i++)
{
printf(“%d\t”, i);
for(int j=0; j<n; j++)
{
printf(“%d “,table[i][j]);
}
printf(“\n”);
}
printf(“\nmax benefit = %d”, a[W]);
}
//hope it helps.
2009-04-18 at 0:12
i am new to the knapsack problem
but it looks like that the lrrh problem described is an unbound knapsack problem.
2009-04-18 at 5:34
yup, it is. The solution I posted up is bounded.
2009-09-28 at 6:08
its cool thank you
2009-09-28 at 6:11
thx you its good
2009-11-04 at 17:47
Thank U so very much .. this post was very helpful in my studies …
2009-11-30 at 9:41
It was very much helpful
Thanks a lot!
2009-12-20 at 10:34
thank you so much..:D
2010-02-04 at 9:29
thanX….nice work….v got A+
2010-02-04 at 9:33
dude ur code had a bug…so i modifyd it….:)
#include
#define MAXWEIGHT 100
int n = 5;
int c[]={2,4,3,5,7}; //cost aka weight
int v[]={3,7,9,8,4}; //value aka benefit
int W=15; //maximum weight can take(bag size)
int main()
{
int table[W][n];
for(int i=0; i<=W; i++)
{
for(int j=0; j<n; j++)
{
table[i][j]=0;
}
}
int a[W]; //this hold the maximum value that can can be obtained using at most i weight
for(int i=0; i<=W; i++)
{
a[i]=0;
}
for(int i=1; i<=W; ++i)
{
for(int j=0; j<n; ++j)
{
if((c[j]<=i)&&(a[i]<=(a[i-c[j]]+v[j]))&&table[i-c[j]][j]!=1)
//c[j]<=i, to allow only if selected weight bucket is less than i
//(a[i]<=(a[i-c[j]]+v[j]), to check if the previous weight bucket has closer value.
//table[i-c[j]][j]!=1 is to prevent the items reuse.
{
for(int k=0; k=a[i])
{
table[i][j]=1;
}
a[i]=newTotalBenefit;
}
}
}
printf(“\t”);
for(int i=0; i<n; i++)
{
printf(“%d “,i);
}
printf(“\n”);
for(int i=0; i<=W; i++)
{
printf(“%d\t”, i);
for(int j=0; j<n; j++)
{
printf(“%d “,table[i][j]);
}
printf(“\n”);
}
printf(“\nmax benefit = %d”, a[W]);
}
//hope it helps.
2010-02-04 at 9:33
dude ur code had a bug…so i modifyd it….:)
#include
#define MAXWEIGHT 10
int n = 5;
int c[]={2,4,3,5,7}; //cost aka weight
int v[]={3,7,9,8,4}; //value aka benefit
int W=15; //maximum weight can take(bag size)
int main()
{
int table[W][n];
for(int i=0; i<=W; i++)
{
for(int j=0; j<n; j++)
{
table[i][j]=0;
}
}
int a[W]; //this hold the maximum value that can can be obtained using at most i weight
for(int i=0; i<=W; i++)
{
a[i]=0;
}
for(int i=1; i<=W; ++i)
{
for(int j=0; j<n; ++j)
{
if((c[j]<=i)&&(a[i]<=(a[i-c[j]]+v[j]))&&table[i-c[j]][j]!=1)
//c[j]<=i, to allow only if selected weight bucket is less than i
//(a[i]<=(a[i-c[j]]+v[j]), to check if the previous weight bucket has closer value.
//table[i-c[j]][j]!=1 is to prevent the items reuse.
{
for(int k=0; k=a[i])
{
table[i][j]=1;
}
a[i]=newTotalBenefit;
}
}
}
printf(“\t”);
for(int i=0; i<n; i++)
{
printf(“%d “,i);
}
printf(“\n”);
for(int i=0; i<=W; i++)
{
printf(“%d\t”, i);
for(int j=0; j<n; j++)
{
printf(“%d “,table[i][j]);
}
printf(“\n”);
}
printf(“\nmax benefit = %d”, a[W]);
}
//hope it helps.
2010-02-04 at 9:35
hey bro..!!!!!!!!
WASSUP???
i didnt understnd ur code man….
plzzzz help…:(
m screwd..:(
2010-02-04 at 9:39
i totaly agree wit anish….
mahambro plz xplain me d code!!!!
2010-02-04 at 10:02
mambro hav u copied ma code…????:@
u cheater…:@
wat d hell u think u duin….???
tak cr…:):)
2010-02-04 at 10:04
actualy i knew dat code b4…
bt thanX 2 mambro…he z real champ….:)
god bles him..ull b a gud programer….:)
thanX again…
2010-02-04 at 10:09
thanX sarvesh…:)
it ws gr8 complemnt…:)
it tuk me yr’s for devising dat logic…:)
bt i think smitaa hav sum probz wid ma code…
n for ur info..i didnt copy ur code…
2010-02-04 at 10:25
Wat a bakwaas code……………
shame on u mahambro…………..
2010-03-01 at 19:40
can anyone explain to me, i am still don’t get this part:
for (i = 1; i <= W; ++i)
for (j = 0; j < n; ++j)
if ((c[j] <= i) &&
(a[i] < a[i – c[j]] + v[j]))
{
a[i] = a[i – c[j]] + v[j];
last_added[i] = j;
}
and why we must use max weight in this code?
it it will get bugged up when u use max weight more than 100?
thanks for the info
2010-03-03 at 14:22
thanks for the source code
2010-03-26 at 10:42
thanks guys; very few c/c++ codes actually have no errors.
I am also understanding it,. very well thank you.
garcias.
2010-06-28 at 3:09
Thanks for the explanation and the implementation, they were very useful; I had been looking for a practical explanation of dynamic programming to solve this problem.
It’s a good post, thanks!
2011-03-12 at 2:00
What you explained is NOT the 0-1 knapsack problem, it is the generic unbounded one. In 0-1 knapsack problem, you are constrained to exactly one or none objects of one kind. In the unbounded knapsack problem, you have an unlimited supply of items (just as you explained in the blog post).
2011-03-28 at 6:08
Hello,
Thank you very much for this explanatory post, specially the part where you explained the output. BTW, if you add a check on line 28 of your code, the algorithm can be modified for use with limited supplies.
Cheers,
Tomas
2011-05-16 at 17:01
Isn’t there a bug in the code that scvalex has posted??
in the part where u include “a[i-c[j]]”, the code assumes that the item having cost c[j] has already been included…what if it was not??
consider c={2,10,13…} and v={2,3,6…}
a[0] and a[1] will be 0, a[2]=2 with cost factor 2, and till a[9] all a[i]s will have cost factor 2 and a[i]=2
a[10]=3 with cost factor 10, and so will a[11], a[12]=5 with cost factor 12, a[13]=6 with cost factor 13… and finally, here’s the problem..
a[14]=a[14-c[j]]+v[j]=a[14-2]+a[2]=a[12]+a[2]
which implies that item having cost 2 is being included twice!!!(since a[12]=a[10]+a[2])… hence i think there is a flaw in the code
2011-05-16 at 17:18
Yes, the code is OK since the item can be included n times because it is the Discrete Knapsack Problem. If you want to limit the items, you’ll need to add an “if” to line 28 in which you check whether the item was already used.
2011-05-20 at 1:35
And what would that “if” be?
“last_added[i] != -1” ?
2011-05-20 at 2:33
If you’re going to add “j” then you can keep a list of j’s that have been added previously to make sure that you don’t go over a certain amount >= 1.
2011-05-20 at 2:59
Would you mind please writing this in the example code? I have tried everything and it doesn’t work.I need some help.
2011-05-20 at 4:27
Sorry that it’s in Basic, but here’s my loop with a check:
2011-10-16 at 21:57
0-1 Knapsack Problem using array
#include
#include
#include
void main()
{
int w[10]={0,5,4,6,3};
int v[10]={0,10,40,30,50};
int n=4,c=10;
int s[20][20];
int keep[20][20],k;
clrscr();
for(int a=0;a<c;a++)
s[0][a]=0;
for(int b=1;b<=n;b++)
{
for(a=0;a<c;a++)
{
if(w[b]s[b-1][a] )
{
s[b][a]=v[b]+s[b-1][a-w[b]];
keep[b][a]=1;
}
else
{
s[b][a]=s[b-1][a];
keep[b][a]=0;
}
}
}
cout<<"\n"; //print set of all possible max value
for(int d=0;d<=n;d++)
{
for(int g=0;g<c;g++)
{
cout<<s[d][g]<<"\t";
}
cout<<"\n";
}
cout<=1;y–)
{
if(keep[y][k-1]==1)
{
cout<<y<<" ";
k=k-w[y];
}
}
cout<<"}";
getch();
}
2014-07-15 at 21:42
If you would like to obtain a great deal from this
piece of writing then you have to apply such methods
to your won weblog.
2017-01-09 at 10:54
It’s an awesome post in support of all the online people; they will take advantage from it I am sure.
2018-04-28 at 6:30
http://Weirdalwiki.com/Enroll_In_Revenue_Coaching_Courses_For_A_Successful_Profession_In_Retailing
The 0-1 Knapsack Problem | Computer programming
2018-04-28 at 6:36
corporate proxy Solicitation
The 0-1 Knapsack Problem | Computer programming
2018-05-17 at 21:33
Corporate proxy solicitation regulations Governing
The 0-1 Knapsack Problem | Computer programming
2018-05-17 at 21:36
Trading Stocks
The 0-1 Knapsack Problem | Computer programming
2018-05-18 at 15:58
http://www.acro3d.com
The 0-1 Knapsack Problem | Computer programming
2018-05-25 at 21:40
Proxy Solicitation Services
The 0-1 Knapsack Problem | Computer programming
2018-06-13 at 5:24
shareholder communications proxy solicitation Rules
The 0-1 Knapsack Problem | Computer programming
2018-06-20 at 15:15
Corporate proxy solicitation investopedia tutorials
The 0-1 Knapsack Problem | Computer programming
2018-06-20 at 15:18
belt gets damaged
The 0-1 Knapsack Problem | Computer programming
2018-06-22 at 2:45
proxy Solicitation firms List
The 0-1 Knapsack Problem | Computer programming
2018-06-28 at 5:31
proxy Solicitation advisors
The 0-1 Knapsack Problem | Computer programming
2018-06-28 at 5:31
paintless Dent removal training
The 0-1 Knapsack Problem | Computer programming
2018-07-15 at 21:48
this guy
The 0-1 Knapsack Problem | Computer programming
2018-07-17 at 3:26
laurel hill proxy solicitation fraud
The 0-1 Knapsack Problem | Computer programming
2018-07-17 at 8:50
broadridge Proxy solicitation Investopedia
The 0-1 Knapsack Problem | Computer programming
2018-07-22 at 13:25
Ncdex Tips
The 0-1 Knapsack Problem | Computer programming
2018-07-22 at 13:30
http://www.Loversick.com
The 0-1 Knapsack Problem | Computer programming
2018-07-22 at 13:56
http://Loversick.com/blogs_post.php?id=161802
The 0-1 Knapsack Problem | Computer programming
2018-07-22 at 13:58
laurel hill proxy solicitation process
The 0-1 Knapsack Problem | Computer programming
2018-07-22 at 14:05
Hydrogen fuel kit for sport utility vehicle (Suv)
The 0-1 Knapsack Problem | Computer programming
2019-03-31 at 6:23
I’m really loving the theme/design of your site.
Do you ever run into any web browser compatibility
problems? A handful of my blog readers have complained about my website not working correctly in Explorer but looks
great in Firefox. Do you have any advice to help fix this
issue?
2019-04-26 at 8:25
At this time it sounds like BlogEngine is the top blogging platform out there right
now. (from what I’ve read) Is that what you are using on your blog?
2020-06-06 at 13:59
Should Terry become a free agent in the summer he could command a hefty signing-on fee of around 锟?00,000 as well as a huge increase in salary.
2020-06-06 at 13:59
Getty Images3Joshua Kimmich in action against Arsenal during demolition job at the EmiratesKimmich g.